Document Open Access Logo

Improved Explicit Hitting-Sets for ROABPs

Authors Zeyu Guo, Rohit Gurjar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.4.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

Zeyu Guo
  • Department of Computer Science, University of Haifa, Israel
Rohit Gurjar
  • Department of Computer Science and Engineering, IIT Bombay, India

Acknowledgements

We thank Nitin Saxena, Sumanta Ghosh, and Pranav Bisht for many helpful discussions about PIT for ROABPs and related models.

Cite As Get BibTex

Zeyu Guo and Rohit Gurjar. Improved Explicit Hitting-Sets for ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.4

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • polynomial identity testing
  • hitting-set
  • ROABP
  • arithmetic branching programs
  • derandomization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669-697, 2015. URL: https://doi.org/10.1137/140975103.
  2. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-Δ formulas. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pages 321-330, 2013. URL: https://doi.org/10.1145/2488608.2488649.
  3. Pranav Bisht and Nitin Saxena. Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs. Electronic Colloquium on Computational Complexity (ECCC), 2020. URL: https://eccc.weizmann.ac.il/report/2020/042.
  4. Mark Braverman, Gil Cohen, and Sumegha Garg. Hitting sets with near-optimal error for read-once branching programs. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), page 353–362, 2018. URL: https://doi.org/10.1145/3188745.3188780.
  5. J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, 1979. URL: https://doi.org/10.1016/0022-0000(79)90044-8.
  6. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
  7. Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena. Towards blackbox identity testing of log-variate circuits. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 54:1-54:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.54.
  8. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pages 867-875, 2014. URL: https://doi.org/10.1145/2591796.2591816.
  9. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pages 243-252, 2013. URL: https://doi.org/10.1109/FOCS.2013.34.
  10. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Theory of Computing, 13(2):1-21, 2017. URL: https://doi.org/10.4086/toc.2017.v013a002.
  11. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Computational Complexity, 26(4):835-880, 2017. URL: https://doi.org/10.1007/s00037-016-0141-z.
  12. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC 1994), pages 356-364, 1994. URL: https://doi.org/10.1145/195058.195190.
  13. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. URL: https://doi.org/10.1007/BF01305237.
  14. Øystein Ore. Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I, 7(15):27, 1922. Google Scholar
  15. Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC 1999), pages 159-168, 1999. URL: https://doi.org/10.1145/301250.301294.
  16. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. URL: https://doi.org/10.1007/s00037-005-0188-8.
  17. Nitin Saxena. Diagonal circuit identity testing and lower bounds. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP 2008), pages 60-71, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_6.
  18. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 99:49-79, 2009. Google Scholar
  19. Nitin Saxena. Progress on polynomial identity testing- II. In Perspectives in Computational Complexity, volume 26 of Progress in Computer Science and Applied Logic, pages 131-146. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-05446-9_7.
  20. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  21. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. URL: https://doi.org/10.1561/0400000039.
  22. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM '79, pages 216-226, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact