License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.30
URN: urn:nbn:de:0030-drops-147231
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14723/
Bhargava, Vishwas ;
Ghosh, Sumanta
Improved Hitting Set for Orbit of ROABPs
Abstract
The orbit of an n-variate polynomial f(x) over a field ? is the set {f(Ax+b) ∣ A ∈ GL(n, ?) and b ∈ ?ⁿ}, 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 fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog 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 a hitting set of size (ndw)^{O(min{w²,dlog 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 [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^{O(w⁶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 [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting.
We prove some new rank concentration results by establishing low-cone concentration for the polynomials over vector spaces, and they strengthen some previously known low-support based rank concentrations shown in [Michael A. 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.
BibTeX - Entry
@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2021.30,
author = {Bhargava, Vishwas and Ghosh, Sumanta},
title = {{Improved Hitting Set for Orbit of ROABPs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {30:1--30:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14723},
URN = {urn:nbn:de:0030-drops-147231},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.30},
annote = {Keywords: Hitting Set, Low Cone Concentration, Orbits, PIT, ROABP}
}
|
Keywords: |
|
Hitting Set, Low Cone Concentration, Orbits, PIT, ROABP |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
15.09.2021 |
