2026-08-17T04:46:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12607 2024-03-06T10:51:14Z ddc:004 open_access

Improved Explicit Hitting-Sets for ROABPs Guo, Zeyu Gurjar, Rohit polynomial identity testing hitting-set ROABP arithmetic branching programs derandomization 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeyu Guo and Rohit Gurjar 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.4 urn:nbn:de:0030-drops-126076 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.4 eng https://creativecommons.org/licenses/by/3.0/legalcode