A Caltech Library Service

Improved Hitting Set for Orbit of ROABPs

Bhargava, Vishwas and Ghosh, Sumanta (2022) Improved Hitting Set for Orbit of ROABPs. Computational Complexity, 31 (2). Art. No. 15. ISSN 1016-3328. doi:10.1007/s00037-022-00230-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:Vishwas Bhargava: Research supported in part by the Simons Collaboration on Algorithms and Geometry and NSF grant CCF-1909683. The authors would like to thank the anonymous referees for useful comments that improved the presentation of the results.
Funding AgencyGrant Number
Simons FoundationUNSPECIFIED
Issue or Number:2
Record Number:CaltechAUTHORS:20221021-259555500.11
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117526
Deposited By: Research Services Depository
Deposited On:27 Oct 2022 20:52
Last Modified:27 Oct 2022 20:52

Repository Staff Only: item control page