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.

Fixed some typos.

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.

Corrected some typos.

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.