{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:08Z","timestamp":1787340308456,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The complexity of Iterated Matrix Multiplication (IMM) 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 $2\\times 2$ 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 \\leq \\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 of these bounds are tight up to constant factors. Our lower bound has the following three consequences for multilinear formula complexity. 1. Depth-reduction: A well-known result of Brent [ J. ACM, 21 (1974), pp. 201--206] 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. 2. Circuits vs. formulas: Any circuit of size $s$ and product-depth $\\Delta$ can be converted into a formula of product-depth $\\Delta$ and size $s^{O(\\Delta)}$. In the multilinear setting, we show that it is not possible to improve on this significantly for small depths. Formally, our results imply that for all large enough $s$ and $\\Delta = o(\\log s\/\\log \\log s)$, there is an explicit multilinear polynomial $P_{s,\\Delta}$ that has a syntactic multilinear circuit of size $s$ and is such that any multilinear formula of product-depth $\\Delta$ computing $P_{s,\\Delta}$ must have size $s^{\\Omega(\\Delta)}$. 3. Separations from general formulas: Shpilka and Yehudayoff [ Found. Trends Theor. Comput. Sci., 5 (2010), pp. 207--388] asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a nontrivial upper bound for ${IMM}_{d}$ implied by a result of Gupta et al. [SIAM J. Comput., 45 (2016), pp. 1064--1079], 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.<\/jats:p>","DOI":"10.1137\/18m1191567","type":"journal-article","created":{"date-parts":[[2019,1,10]],"date-time":"2019-01-10T11:08:26Z","timestamp":1547118506000},"page":"70-92","source":"Crossref","is-referenced-by-count":5,"title":["Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications"],"prefix":"10.1137","volume":"48","author":[{"given":"Suryajith","family":"Chillara","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,1,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay,\n                      Arithmetic circuits: A chasm at depth four\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 67-75,https:\/\/doi.org\/10.1109\/FOCS.2008.32.","DOI":"10.1109\/FOCS.2008.32"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"atypb3","unstructured":"N. Alon, M. Kumar, and B. L. Volk,\n                      Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits\n                      ,https:\/\/mrinalkr.bitbucket.io\/papers\/synt-multilinear.pdf, 2017."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"atypb6","unstructured":"D. P. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, Cambridge, 2009,http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item2327542\/."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"Z. Dvir, G. Malod, S. Perifel, and A. Yehudayoff,\n                      Separating multilinear branching programs and formulas\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012, pp. 615-624,https:\/\/doi.org\/10.1145\/2213977.2214034.","DOI":"10.1145\/2213977.2214034"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"H. Fournier, N. Limaye, G. Malod, and S. Srinivasan,\n                      Lower bounds for depth 4 formulas computing iterated matrix multiplication\n                      , in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 2014, pp. 128-135,http:\/\/doi.acm.org\/10.1145\/2591796.2591824.","DOI":"10.1145\/2591796.2591824"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/140957123"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0007-3"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"N. Kayal, N. Limaye, C. Saha, and S. Srinivasan,\n                      An exponential lower bound for homogeneous depth four arithmetic circuits\n                      , in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2014, pp. 61-70,https:\/\/doi.org\/10.1109\/FOCS.2014.15.","DOI":"10.1109\/FOCS.2014.15"},{"key":"atypb13","unstructured":"N. Kayal, V. Nair, and C. Saha,\n                      Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits\n                      , in Proceedings of the 33rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2016, 46,https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.46."},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"N. Kayal, C. Saha, and S. Tavenas,\n                      On the size of homogeneous and of depth four formulas with low individual degree\n                      , in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016, pp. 626-632,https:\/\/doi.org\/10.1145\/2897518.2897550.","DOI":"10.1145\/2897518.2897550"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Kumar and S. Saraf,\n                      On the power of homogeneous depth 4 arithmetic circuits\n                      , in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2014, pp. 364-373,https:\/\/doi.org\/10.1109\/FOCS.2014.46.","DOI":"10.1109\/FOCS.2014.46"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.42"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a006"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2535928"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0254-0"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"B. Rossman,\n                      The average sensitivity of bounded-depth formulas\n                      , in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2015, pp. 424-430,https:\/\/doi.org\/10.1109\/FOCS.2015.33.","DOI":"10.1109\/FOCS.2015.33"},{"key":"atypb24","first-page":"50","author":"Rossman B.","year":"2017","journal-title":"ICALP."},{"key":"atypb25","unstructured":"R. Saptharishi,\n                      A Survey of Known Lower Bounds in Arithmetic Circuit Complexity\n                      , Github Survey, 2015,https:\/\/github.com\/dasarpmar\/lowerbounds-survey."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009105"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1191567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:18Z","timestamp":1787336958000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1191567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1191567"],"URL":"https:\/\/doi.org\/10.1137\/18m1191567","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}