Document Open Access Logo

Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs

Authors Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.323.pdf
  • Filesize: 0.57 MB
  • 24 pages

Document Identifiers

Author Details

Rohit Gurjar
Arpita Korwar
Nitin Saxena
Thomas Thierauf

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 323-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CCC.2015.323

Abstract

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).
Keywords
  • PIT
  • Hitting-set
  • Sum of ROABPs
  • Evaluation Dimension
  • Rank Concentration

Metrics

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

References

  1. Leonard M. Adleman and Hendrik W. Lenstra. Finding irreducible polynomials over finite fields. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC'86, pages 350-355, New York, NY, USA, 1986. ACM. Google Scholar
  2. 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
  3. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. Electronic Colloquium on Computational Complexity (ECCC), 21:85, 2014. (to appear in SICOMP, 2015). Google Scholar
  4. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth- formulas. In STOC, pages 321-330, 2013. Google Scholar
  5. Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC'88, pages 301-309, New York, NY, USA, 1988. ACM. Google Scholar
  6. Rafael Mendes de Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential size hitting sets for bounded depth multilinear formulas. Electronic Colloquium on Computational Complexity (ECCC), 21:157, 2014. (to appear in CCC'15). Google Scholar
  7. Zeev Dvir and Amir Shpilka. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404-1434, 2007. Google Scholar
  8. Michael A. Forbes. Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. PhD thesis, MIT, 2014. 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 2014, New York, NY, USA, May 31 - June 03, 2014, pages 867-875, 2014. Google Scholar
  10. Michael A. Forbes and Amir Shpilka. On identity testing of tensors, low-rank recovery and compressed sensing. In STOC, pages 163-172, 2012. Google Scholar
  11. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. CoRR, abs/1209.2408, 2012. Google Scholar
  12. 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. Google Scholar
  13. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. FOCS, pages 578-587, 2013. Google Scholar
  14. Maurice J. Jansen, Youming Qiao, and Jayalal Sarma. Deterministic identity testing of read-once algebraic branching programs. Electronic Colloquium on Computational Complexity (ECCC), 17:84, 2010. 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. Zohar Shay Karnin and Amir Shpilka. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333-364, 2011. Google Scholar
  17. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth 3 circuits. In FOCS, pages 198-207, 2009. Google Scholar
  18. Neeraj Kayal and Nitin Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115-138, 2007. Google Scholar
  19. Adam Klivans and Daniel A. Spielman. Randomness efficient identity testing of multivariate polynomials. In STOC, pages 216-223, 2001. Google Scholar
  20. Vineet Nair and Chandan Saha. Personal communication, 2014. Google Scholar
  21. 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
  22. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. Google Scholar
  23. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. Google Scholar
  24. Petr Savický and Ingo Wegener. Efficient algorithms for the transformation between different types of binary decision diagrams. Acta Informatica, 34(4):245-256, 1997. Google Scholar
  25. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 99:49-79, 2009. Google Scholar
  26. Nitin Saxena. Progress on polynomial identity testing-II. In Perspectives in Computational Complexity, pages 131-146. Birkhäuser Basel, 2014. Google Scholar
  27. Nitin Saxena and Comandur Seshadhri. An almost optimal rank bound for depth-3 identities. SIAM J. Comput., 40(1):200-224, 2011. Google Scholar
  28. Nitin Saxena and Comandur Seshadhri. Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn't matter. SIAM J. Comput., 41(5):1285-1298, 2012. Google Scholar
  29. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, October 1980. Google Scholar
  30. 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. Google Scholar
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 Imprint Privacy Contact