Document Open Access Logo

Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

Authors Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.21.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Suryajith Chillara
Nutan Limaye
Srikanth Srinivasan

Cite As Get BibTex

Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.21

Abstract

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within P. In this paper, we study the algebraic formula complexity of multiplying d many 2x2 matrices, denoted  IMM_d, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear.

Formally, for each depth Delta <= log d, we show that any product-depth Delta multilinear formula for IMM_d must have size exp(Omega(Delta d^{1/Delta})). It also follows from this that any multilinear circuit of product-depth Delta for the same polynomial of the above form must have a size of exp(Omega(d^{1/Delta})). In particular, any polynomial-sized multilinear formula for IMM_d must have depth Omega(log d), and any polynomial-sized multilinear circuit for IMM_d must have depth Omega(log d/log log d). Both these bounds are tight up to constant factors.

Our lower bound has the following consequences for multilinear formula complexity. 

Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size s can be converted to one of size s^{O(1)} and depth O(log s); further, this reduction continues to hold for multilinear formulas. On the other hand, our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to o(log s) without a superpolynomial blow-up in size.

Separations from general formulas: Shpilka and Yehudayoff (FnTTCS 2010) asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a non-trivial upper bound for IMM_d implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size s and product-depth Delta = o(log s), general formulas of size s and product-depth Delta cannot be converted to multilinear formulas of size s^{O(1)} and product-depth Delta, when the underlying field has characteristic zero.

Subject Classification

Keywords
  • Algebraic circuit complexity
  • Multilinear formulas
  • Lower Bounds

Metrics

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

References

  1. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 67-75. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.32.
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. URL: http://dx.doi.org/10.1145/1706591.1706594.
  3. Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201-206, 1974. URL: http://dx.doi.org/10.1145/321812.321815.
  4. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth multilinear formula lower bounds for iterated matrix multiplication, with applications. Electronic Colloquium on Computational Complexity (ECCC), 24:156, 2017. URL: https://eccc.weizmann.ac.il/report/2017/156.
  5. 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: http://dx.doi.org/10.1145/2213977.2214034.
  6. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 128-135. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591824.
  7. 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: http://dx.doi.org/10.1137/140957123.
  8. Pavel Hrubeš and Amir Yehudayoff. Homogeneous formulas and symmetric polynomials. Computational Complexity, 20(3):559-578, 2011. Google Scholar
  9. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 61-70. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.15.
  10. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (roabps) and multilinear depth three circuits. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 46:1-46:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.46.
  11. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the size of homogeneous and of depth four formulas with low individual degree. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 626-632. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897550.
  12. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 364-373. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.46.
  13. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. URL: http://dx.doi.org/10.1007/BF01294256.
  14. Ran Raz. Multilinear-nc neq multilinear-nc. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 344-351. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.42.
  15. Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(6):121-135, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a006.
  16. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1-40:15, 2013. URL: http://dx.doi.org/10.1145/2535928.
  17. Ran Raz, Amir Shpilka, and Amir Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. Comput., 38(4):1624-1647, 2008. URL: http://dx.doi.org/10.1137/070707932.
  18. Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008. URL: http://dx.doi.org/10.1007/s00037-008-0254-0.
  19. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0270-8.
  20. Benjamin Rossman. The average sensitivity of bounded-depth formulas. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 424-430. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.33.
  21. Benjamin Rossman and Srikanth Srinivasan. Separation of ac^0[oplus] formulas and circuits. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 50:1-50:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.50.
  22. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  23. 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: http://dx.doi.org/10.1561/0400000039.
  24. Philip M Spira. Computation times of arithmetic and boolean functions in (d, r) circuits. IEEE Transactions on Computers, 100(6):552-555, 1973. Google Scholar
  25. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.09.004.
  26. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641-644, 1983. URL: http://dx.doi.org/10.1137/0212043.
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