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.