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/
Go to the corresponding LIPIcs Volume Portal

Guo, Zeyu ; Gurjar, Rohit

Improved Explicit Hitting-Sets for ROABPs

pdf-format:
LIPIcs-APPROX4.pdf (0.6 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI