Document Open Access Logo

A Quadratic Lower Bound for Algebraic Branching Programs

Authors Prerona Chatterjee , Mrinal Kumar, Adrian She, Ben Lee Volk

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.2.pdf
  • Filesize: 0.54 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic Branching Programs
  • Lower Bound

Metrics

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

Abstract

We show that any Algebraic Branching Program (ABP) computing the polynomial ∑_{i=1}^n xⁿ_i has at least Ω(n²) vertices. This improves upon the lower bound of Ω(nlog n), which follows from the classical result of Baur and Strassen [Volker Strassen, 1973; Walter Baur and Volker Strassen, 1983], and extends the results of Kumar [Mrinal Kumar, 2019], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial.
Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial ∑_{i=1}^n xⁿ_i can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial ∑_{i=1}^n xⁿ_i + ε(𝐱), for a structured "error polynomial" ε(𝐱). To complete the proof, we then observe that the lower bound in [Mrinal Kumar, 2019] is robust enough and continues to hold for all polynomials ∑_{i=1}^n xⁿ_i + ε(𝐱), where ε(𝐱) has the appropriate structure.

Cite As Get BibTex

Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.2

Author Details

Prerona Chatterjee
  • Tata Institute of Fundamental Research, Mumbai, India
Mrinal Kumar
  • Department of Computer Science &Engineering, IIT Bombay, India
Adrian She
  • Department of Computer Science, University of Toronto, Canada
Ben Lee Volk
  • Center for the Mathematics of Information, California Institute of Technology, Pasadena, CA, USA

Funding

  • Chatterjee, Prerona: Research supported by the Department of Atomic Energy, Government of India, under project no. 12-R&D-TFR-5.01-0500.

Acknowledgements

We are thankful to Ramprasad Saptharishi for helpful discussions at various stages of this work. A part the second author’s work was done during a postdoctoral stay at University of Toronto.

References

  1. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317-330, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  2. Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 80-86. ACM, 1983. URL: https://doi.org/10.1145/800061.808735.
  3. Michael Ben-Or. Algebraic computation trees in characteristi pgreater0 (extended abstract). In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 534-539. IEEE Computer Society, 1994. URL: https://doi.org/10.1109/SFCS.1994.365738.
  4. Jin-yi Cai, Xi Chen, and Dong Li. Quadratic lower bound for permanent vs. determinant in any characteristic. Comput. Complex., 19(1):37-56, 2010. URL: https://doi.org/10.1007/s00037-009-0284-2.
  5. Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A quadratic lower bound for algebraic branching programs and formulas. CoRR, abs/1911.11793, 2019. URL: http://arxiv.org/abs/1911.11793.
  6. David A. Cox, John B. Little, and Donal O'Shea. Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer, 2007. URL: https://doi.org/10.1007/978-0-387-35651-8.
  7. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 615-624. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214034.
  8. Paul Erdős, Ronald L. Graham, and Endre Szemerédi. On sparse graphs with dense long paths. Computers &Mathematics with Applications, 1(3):365-369, 1975. URL: https://doi.org/10.1016/0898-1221(75)90037-1.
  9. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. URL: https://doi.org/10.1137/140957123.
  10. Pavel Hrubes and Amir Yehudayoff. On isoperimetric profiles and computational complexity. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 89:1-89:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.89.
  11. Kyriakos Kalorkoti. A Lower Bound for the Formula Size of Rational Functions. SIAM Journal on Computing, 14(3):678-687, 1985. URL: https://doi.org/10.1137/0214050.
  12. Mauricio Karchmer and Avi Wigderson. On span programs. In Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, pages 102-111. IEEE Computer Society, 1993. URL: https://doi.org/10.1109/SCT.1993.336536.
  13. Mrinal Kumar. A quadratic lower bound for homogeneous algebraic branching programs. Computational Complexity, 28(3):409-435, 2019. URL: https://doi.org/10.1007/s00037-019-00186-3.
  14. Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci., 1997, 1997. URL: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html.
  15. Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices, 2004(79):4241-4253, 2004. Google Scholar
  16. Eduard Ivanovich Nechiporuk. On a boolean function. Dokl. Akad. Nauk SSSR, 169:765-766, 1966. URL: http://mi.mathnet.ru/dan32449.
  17. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418. ACM, 1991. URL: https://doi.org/10.1145/103418.103462.
  18. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. Available on http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.2644. URL: https://doi.org/10.1007/BF01294256.
  19. Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(6):121-135, 2006. URL: https://doi.org/10.4086/toc.2006.v002a006.
  20. Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008. URL: https://doi.org/10.1007/s00037-008-0254-0.
  21. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  22. Justin R. Smith. Introduction to Algebraic Geometry. Textbooks in Mathematics. Taylor &Francis, 2014. URL: https://books.google.com/books?id=zx7usgEACAAJ.
  23. Roman Smolensky. Easy lower bound for a strange computational model. Computational Complexity, 6(3):213-216, 1997. URL: https://doi.org/10.1007/BF01294255.
  24. Volker Strassen. Die berechnungskomplexität von elementarsymmetrischen funktionen und von interpolationskoeffizienten. Numerische Mathematik, 20(3):238-251, June 1973. URL: https://doi.org/10.1007/BF01436566.
  25. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. URL: http://eudml.org/doc/151394.
  26. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Jozef Gruska, editor, Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings, volume 53 of Lecture Notes in Computer Science, pages 162-176. Springer, 1977. URL: https://doi.org/10.1007/3-540-08353-7_135.
  27. Akihiro Yabe. Bi-polynomial rank and determinantal complexity. CoRR, abs/1504.00151, 2015. URL: http://arxiv.org/abs/1504.00151.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact