Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR21-062 | 13th July 2021 15:49

#### Improved Hitting Set for Orbit of ROABPs

Revision #2
Authors: Vishwas Bhargava, Sumanta Ghosh
Accepted on: 13th July 2021 15:50
Keywords:

Abstract:

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over field with characteristic zero or greater than $d$, we construct a hitting set of size $(ndw)^{O(w^2\log n\cdot \min\{w^2, d\log w\})}$ for the orbit of ROABPs in unknown variable order where $d$ is the individual degree and $w$ is the width of ROABPs. We also give hitting set of size $(ndw)^{O(\min\{w^2,d\log w\})}$ for the orbit of polynomials computed by $w$-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey \cite{Saha-Thankey'21} who gave an $(ndw)^{O(d\log w)}$ size hitting set for the orbit of commutative ROABPs (a subclass of \textit{any-order} ROABPs) and $(nw)^{O(w^6\log n)}$ size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance $d>n$, was asked as an open problem by \cite{Saha-Thankey'21} and this work solves it in small width setting.

We prove some new rank concentration results by establishing \emph{low-cone concentration} for the polynomials over vector spaces, and they strengthen some previously known \emph{low-support} based rank concentrations shown in \cite{FSS14}. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.

Changes to previous version:

Fixed some typos.

Revision #1 to TR21-062 | 29th May 2021 14:31

#### Improved Hitting Set for Orbit of ROABPs

Revision #1
Authors: Vishwas Bhargava, Sumanta Ghosh
Accepted on: 29th May 2021 14:31
Keywords:

Abstract:

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over field with characteristic zero or greater than $d$, we construct a hitting set of size $(ndw)^{O(w^2\log n\cdot \min\{w^2, d\log w\})}$ for the orbit of ROABPs in unknown variable order where $d$ is the individual degree and $w$ is the width of ROABPs. We also give hitting set of size $(ndw)^{O(\min\{w^2,d\log w\})}$ for the orbit of polynomials computed by $w$-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey \cite{Saha-Thankey'21} who gave an $(ndw)^{O(d\log w)}$ size hitting set for the orbit of commutative ROABPs (a subclass of \textit{any-order} ROABPs) and $(nw)^{O(w^6\log n)}$ size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance $d>n$, was asked as an open problem by \cite{Saha-Thankey'21} and this work solves it in small width setting.

We prove some new rank concentration results by establishing \emph{low-cone concentration} for the polynomials over vector spaces, and they strengthen some previously known \emph{low-support} based rank concentrations shown in \cite{FSS14}. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.

Changes to previous version:

Corrected some typos.

### Paper:

TR21-062 | 29th April 2021 09:12

#### Improved Hitting Set for Orbit of ROABPs

TR21-062
Authors: Vishwas Bhargava, Sumanta Ghosh
Publication: 2nd May 2021 10:04
The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over field with characteristic zero or greater than $d$, we construct a hitting set of size $(ndw)^{O(w^2\log n\cdot \min\{w^2, d\log w\})}$ for the orbit of ROABPs in unknown variable order where $d$ is the individual degree and $w$ is the width of ROABPs. We also give hitting set of size $(ndw)^{O(\min\{w^2,d\log w\})}$ for the orbit of polynomials computed by $w$-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey \cite{Saha-Thankey'21} who gave an $(ndw)^{O(d\log w)}$ size hitting set for the orbit of commutative ROABPs (a subclass of \textit{any-order} ROABPs) and $(nw)^{O(w^6\log n)}$ size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance $d>n$, was asked as an open problem by \cite{Saha-Thankey'21} and this work solves it in small width setting.