Guo, Zeyu ;
Gurjar, Rohit
Improved Explicit HittingSets for ROABPs
Abstract
We give improved explicit constructions of hittingsets for readonce oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hittingset has size polynomial in (nr)^{(log n)/(max{1, log log nlog 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 hittingsets for sum of several ROABPs. In particular, when the characteristic of the field is zero or large enough, we give polynomialsize explicit hittingsets for sum of constantly many logvariate ROABPs of width r = 2^{O(log d/log log d)}.
Finally, we give improved explicit hittingsets for polynomials computable by widthr ROABPs in any variable order, also known as anyorder ROABPs. Our hittingset 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 hittingsets 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 HittingSets for ROABPs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {4:14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12607},
URN = {urn:nbn:de:0030drops126076},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.4},
annote = {Keywords: polynomial identity testing, hittingset, ROABP, arithmetic branching programs, derandomization}
}
11.08.2020
Keywords: 

polynomial identity testing, hittingset, ROABP, arithmetic branching programs, derandomization 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 