Document Open Access Logo

Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs

Authors Rohit Gurjar, Arpita Korwar, Nitin Saxena

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2016.29.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • PIT
  • hitting-set
  • constant-width ROABPs
  • commutative ROABPs

Metrics

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

Abstract

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost (nw)^{O(log(n))}, where n is the number of variables and w is the width of the ROABP. Even for a constant-width ROABP, nothing better than a quasi-polynomial bound was known. We improve the hitting-set complexity for the known-order case to n^{O(log(w))}. In particular, this gives the first polynomial time hitting-set for constant-width ROABP (known-order). However, our hitting-set works only over those fields whose characteristic is zero or large enough. To construct the hitting-set, we use the concept of the rank of partial derivative matrix. Unlike previous approaches whose starting point is a monomial map, we use a polynomial map directly.

The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost d^{O(log(w))}(nw)^{O(log(log(w)))}, where d is the individual degree. We improve this hitting-set complexity to (ndw)^{O(log(log(w)))}. We get this by achieving rank concentration more efficiently.

Cite As Get BibTex

Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.29

Author Details

Rohit Gurjar
Arpita Korwar
Nitin Saxena

References

  1. Manindra Agrawal. Proving lower bounds via pseudo-random generators. In FSTTCS, volume 3821 of Lecture Notes in Computer Science, pages 92-105, 2005. Google Scholar
  2. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669-697, 2015. URL: http://dx.doi.org/10.1137/140975103.
  3. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-formulas. In STOC, pages 321-330, 2013. Google Scholar
  4. Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity testing and lower bounds for read-k oblivious algebraic branching programs. In Computational Complexity Conference (CCC), 2016. Google Scholar
  5. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009. Google Scholar
  6. Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54-58, 1992. Google Scholar
  7. Rafael Mendes de Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential size hitting sets for bounded depth multilinear formulas. In 30th Conference on Computational Complexity (CCC), pages 304-322, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.304.
  8. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  9. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Symposium on Theory of Computing (STOC), New York, NY, USA, May 31 - June 03, 2014, pages 867-875, 2014. Google Scholar
  10. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In FOCS, pages 243-252, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.34.
  11. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 323-346, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.323.
  12. J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC'80, pages 262-272, New York, NY, USA, 1980. ACM. URL: http://dx.doi.org/10.1145/800141.804674.
  13. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 111-119, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.78.
  14. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC, pages 356-364, New York, NY, USA, 1994. ACM. Google Scholar
  15. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. STOC, pages 355-364, 2003. Google Scholar
  16. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (roabps) and multilinear depth three circuits. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 46:1-46:15, 2016. Google Scholar
  17. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.041.
  18. Noam Nisan. Pseudorandom generators for space-bounded computations. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC'90, pages 204-212, New York, NY, USA, 1990. ACM. URL: http://dx.doi.org/10.1145/100216.100242.
  19. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd ACM Symposium on Theory of Computing, ACM Press, pages 410-418, 1991. Google Scholar
  20. Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 159-168, 1999. URL: http://dx.doi.org/10.1145/301250.301294.
  21. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. Google Scholar
  22. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, October 1980. Google Scholar
  23. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM'79, pages 216-226, London, UK, UK, 1979. Springer-Verlag. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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