Document Open Access Logo

A Depth-Five Lower Bound for Iterated Matrix Multiplication

Authors Suman K. Bera, Amit Chakrabarti

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.183.pdf
  • Filesize: 476 kB
  • 15 pages

Document Identifiers

Author Details

Suman K. Bera
Amit Chakrabarti

Cite As Get BibTex

Suman K. Bera and Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 183-197, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.183

Abstract

We prove that certain instances of the iterated matrix multiplication (IMM) family of polynomials with N variables and degree n require N^(Omega(sqrt(n))) gates when expressed as a homogeneous depth-five Sigma Pi Sigma Pi Sigma arithmetic circuit with the bottom fan-in bounded by N^(1/2-epsilon). By a depth-reduction result of Tavenas, this size lower bound is optimal and can be achieved by the weaker class of homogeneous depth-four Sigma Pi Sigma Pi circuits.

Our result extends a recent result of Kumar and Saraf, who gave the same N^(Omega(sqrt(n))) lower bound for homogeneous depth-four Sigma Pi Sigma Pi circuits computing IMM. It is analogous to a recent result of Kayal and Saha, who gave the same lower bound for homogeneous Sigma Pi Sigma Pi Sigma circuits (over characteristic zero) with bottom fan-in at most N^(1-epsilon), for the harder problem of computing certain polynomials defined by Nisan-Wigderson designs.

Subject Classification

Keywords
  • arithmetic circuits
  • iterated matrix multiplication
  • depth five circuits
  • lower bound

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 Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pages 67-75, 2008. Google Scholar
  2. Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inform. Process. Lett., 18(3):147-150, 1984. Google Scholar
  3. Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  4. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In Proc. 46th Annual ACM Symposium on the Theory of Computing, pages 128-135, 2014. Google Scholar
  5. Dima Grigoriev and Marek Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In Proc. 30th Annual ACM Symposium on the Theory of Computing, pages 577-582, 1998. Google Scholar
  6. Dima Grigoriev and Alexander Razborov. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Applicable Algebra in Engineering, Communication and Computing, 10(6):465-487, 2000. Google Scholar
  7. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. In Proc. 28th Annual IEEE Conference on Computational Complexity, pages 65-73, 2013. Google Scholar
  8. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science, pages 578-587, 2013. Google Scholar
  9. Kumar Joag-Dev and Frank Proschan. Negative association of random variables, with applications. Ann. Stat., 11(1):286-295, 1983. Google Scholar
  10. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science, 2014. Google Scholar
  11. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In Proc. 46th Annual ACM Symposium on the Theory of Computing, pages 119-127, 2014. Google Scholar
  12. Neeraj Kayal and Chandan Saha. Lower bounds for depth three arithmetic circuits with small bottom fanin. Technical Report TR14-089, ECCC, 2014. Google Scholar
  13. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Proc. 46th Annual ACM Symposium on the Theory of Computing, pages 146-153, 2014. Google Scholar
  14. Neeraj Kayal and Ramprasad Saptharishi. A selection of lower bounds for arithmetic circuits, pages 77-115. Springer Verlag, April 2014. Google Scholar
  15. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56-65, 2012. Google Scholar
  16. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science, 2014. Google Scholar
  17. Noam Nisan and Avi Wigderson. Hardness vs. randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  18. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. In Proc. 36th Annual IEEE Symposium on Foundations of Computer Science, pages 16-–25, 1995. Google Scholar
  19. Ramprasad Saptharishi. Recent progress on arithmetic circuit lower bounds. Bulletin of the EATCS, 114, 2014. Google Scholar
  20. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3-4):207-388, 2010. Google Scholar
  21. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. In Proc. 38th International Symposium on Mathematical Foundations of Computer Science, pages 813-824, 2013. Google Scholar
  22. L. G. Valiant. Completeness classes in algebra. In Proc. 11th Annual ACM Symposium on the Theory of Computing, pages 249-261, 1979. Google Scholar
  23. 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. 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 About DROPS Imprint Privacy Contact