Improved Hitting Set for Orbit of ROABPs

Abstract

The orbit of an n-variate polynomial f(x) over a field F is the set {f(Ax + b) ∣ A∈GL(n,F) and b ∈ Fⁿ}, and the orbit of a polynomial class is the union of orbits of 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 fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^[O(w2logn⋅min{w2,dlogw})] 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 a hitting set of size (ndw)^[O(min{w2,dlogw})] for the orbit of polynomials computed by width-w ROABPs in any variable order. Our hitting sets improve upon the results of Saha & Thankey (2021) who gave an (ndw)^[O(dlogw)] size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^[O(w6logn)] 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 Saha & Thankey (2021) and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for polynomials over vector spaces, and they strengthen some previously known low-support-based rank concentration results shown in Forbes et al. (2013). 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.

Additional details