License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.4
URN: urn:nbn:de:0030-drops-126076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12607/
Guo, Zeyu ;
Gurjar, Rohit
Improved Explicit Hitting-Sets for ROABPs
Abstract
We give improved explicit constructions of hitting-sets for read-once oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hitting-set has size polynomial in (nr)^{(log n)/(max{1, log log n-log log r})}d over a field whose characteristic is zero or large enough, where n is the number of variables, d is the individual degree, and r is the width of the ROABP. A similar improved construction works over fields of arbitrary characteristic with a weaker size bound.
Based on a result of Bisht and Saxena (2020), we also give an improved explicit construction of hitting-sets for sum of several ROABPs. In particular, when the characteristic of the field is zero or large enough, we give polynomial-size explicit hitting-sets for sum of constantly many log-variate ROABPs of width r = 2^{O(log d/log log d)}.
Finally, we give improved explicit hitting-sets for polynomials computable by width-r ROABPs in any variable order, also known as any-order ROABPs. Our hitting-set has polynomial size for width r up to 2^{O(log(nd)/log log(nd))} or 2^{O(log^{1-ε} (nd))}, depending on the characteristic of the field. Previously, explicit hitting-sets of polynomial size are unknown for r = ω(1).
BibTeX - Entry
@InProceedings{guo_et_al:LIPIcs:2020:12607,
author = {Zeyu Guo and Rohit Gurjar},
title = {{Improved Explicit Hitting-Sets for ROABPs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {4:1--4:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12607},
URN = {urn:nbn:de:0030-drops-126076},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.4},
annote = {Keywords: polynomial identity testing, hitting-set, ROABP, arithmetic branching programs, derandomization}
}
Keywords: |
|
polynomial identity testing, hitting-set, ROABP, arithmetic branching programs, derandomization |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
11.08.2020 |