{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:45Z","timestamp":1781078205575,"version":"3.54.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T00:00:00Z","timestamp":1731283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DST-SERB","award":["CRG\/2020\/45, and JCB\/2022\/57"],"award-info":[{"award-number":["CRG\/2020\/45, and JCB\/2022\/57"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"\n We show that any product-depth \u0394 algebraic circuit for the Iterated Matrix Multiplication polynomial IMM\n \n n, d<\/jats:italic>\n <\/jats:sub>\n (when\n d<\/jats:italic>\n =\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n \/log log\n n<\/jats:italic>\n ) must be of size at least\n \n \\(n^{\\Omega (d^{1\/(\\varphi ^2)^{\\Delta }})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where \u03c6 = 1.618 \u2026 is the golden ratio. This improves the recent breakthrough result of Limaye, Srinivasan, and Tavenas (FOCS\u201921), who showed a super polynomial lower bound of the form\n \n \\(n^{\\Omega (d^{1\/4^{\\Delta }})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for constant-depth circuits.\n <\/jats:p>\n \n One crucial idea of the (LST21) result was to use set-multilinear polynomials where each set in the variables\u2019 underlying partition could be of different sizes. By picking the set sizes more carefully (depending on the depth we are working with), we first show that any product-depth\n \n \\(\\Delta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n set-multilinear<\/jats:italic>\n circuit for\n \n \\(\\mathrm{IMM}_{n,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (when\n \n \\(d = O(\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) needs size at least\n \n \\(n^{\\Omega (d^{1\/\\varphi ^{\\Delta }})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This improves the\n \n \\(n^{\\Omega (d^{1\/2^{\\Delta }})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n lower bound of (LST21). We then use their Hardness Escalation technique to lift this to general circuits.\n <\/jats:p>\n \n We also show that these techniques cannot improve our lower bound significantly. For the\n specific<\/jats:italic>\n two set sizes used in (LST21), they showed that their lower bound cannot be improved. We show that for any\n \n \\(d^{o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n set sizes (out of maximum possible\n d<\/jats:italic>\n ), the scope for improving our lower bound is minuscule. There exists a set-multilinear circuit that has product-depth\n \n \\(\\Delta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and size almost matching our lower bound such that the value of the measure used to prove the lower bound is maximum for this circuit. This results in a barrier to further improvement using the same measure.\n <\/jats:p>","DOI":"10.1145\/3689957","type":"journal-article","created":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:10:12Z","timestamp":1725552612000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6920-4998","authenticated-orcid":false,"given":"C.S.","family":"Bhargav","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0929-6082","authenticated-orcid":false,"given":"Sagnik","family":"Dutta","sequence":"additional","affiliation":[{"name":"Computer Science, Chennai Mathematical Institute, Chennai India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6931-898X","authenticated-orcid":false,"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Walter Baur and Volker Strassen. 1983. The complexity of partial derivatives. Theoretical Computer Science 22 3 (1983) 317\u2013330.","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Xi Chen Neeraj Kayal and Avi Wigderson. 2010. Partial derivatives in arithmetic complexity and beyond. Foundations and Trends Theoretical Computer Science 6 1-2 (2010) front matter 1\u2013138 (2011).","DOI":"10.1561\/0400000043"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"Suryajith Chillara Nutan Limaye and Srikanth Srinivasan. 2019. Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications. SIAM Journal on Computing 48 1 (2019) 70\u201392.","DOI":"10.1137\/18M1191567"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"Herv\u00e9 Fournier Nutan Limaye Guillaume Malod and Srikanth Srinivasan. 2015. Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM Journal on Computing 44 5 (2015) 1173\u20131201.","DOI":"10.1137\/140990280"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"Ankit Gupta Pritish Kamath Neeraj Kayal and Ramprasad Saptharishi. 2014. Approaching the chasm at depth four. Journal of the ACM 61 6 (2014) Art. 33 16.","DOI":"10.1145\/2629541"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Ankit Gupta Pritish Kamath Neeraj Kayal and Ramprasad Saptharishi. 2016. Arithmetic circuits: A chasm at depth 3. SIAM Journal on Computing 45 3 (2016) 1064\u20131079.","DOI":"10.1137\/140957123"},{"key":"e_1_3_2_10_2","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"Art. 23, 31","volume-title":"Proceedings of the 35th Computational Complexity Conference","volume":"169","author":"Gupta Nikhil","year":"2020","unstructured":"Nikhil Gupta, Chandan Saha, and Bhargav Thankey. 2020. A super-quadratic lower bound for depth four arithmetic circuits. In Proceedings of the 35th Computational Complexity Conference. LIPIcs. Leibniz Int. Proc. Inform., Vol. 169. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. 23, 31."},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","unstructured":"K. A. Kalorkoti. 1985. A lower bound for the formula size of rational functions. SIAM Journal on Computing 14 3 (1985) 678\u2013687.","DOI":"10.1137\/0214050"},{"key":"e_1_3_2_12_2","unstructured":"Neeraj Kayal. 2012. An exponential lower bound for the sum of powers of bounded degree polynomials. (2012)."},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal Nutan Limaye Chandan Saha and Srikanth Srinivasan. 2017. An exponential lower bound for homogeneous depth four arithmetic formulas. SIAM Journal on Computing 46 1 (2017) 307\u2013335.","DOI":"10.1137\/151002423"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591847"},{"key":"e_1_3_2_15_2","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"Art. No. 33, 15","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming","volume":"55","author":"Kayal Neeraj","year":"2016","unstructured":"Neeraj Kayal, Chandan Saha, and S\u00e9bastien Tavenas. 2016. An almost cubic lower bound for depth three arithmetic circuits. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming. LIPIcs. Leibniz Int. Proc. Inform., Vol. 55. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 33, 15."},{"key":"e_1_3_2_16_2","unstructured":"Neeraj Kayal Chandan Saha and S\u00e9bastien Tavenas. 2018. On the size of homogeneous and of depth-four formulas with low individual degree. Theory of Computing 14 (2018) Paper No. 16 46."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Pascal Koiran. 2012. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science 448 (2012) 56\u201365.","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.46"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar and Shubhangi Saraf. 2015. The limits of depth reduction for arithmetic formulas: it\u2019s all about the top fan-in. SIAM Journal on Computing 44 6 (2015) 1601\u20131625.","DOI":"10.1137\/140999220"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.38"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.32"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00083"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05446-9_4"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-99970-3"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Noam Nisan and Avi Wigderson. 1995. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity 6 3 (1995) 217\u2013234.","DOI":"10.1007\/BF01294256"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","unstructured":"Ran Raz. 2006. Separation of multilinear circuit and formula size. Theory of Computing 2 (2006) 121\u2013135.","DOI":"10.4086\/toc.2006.v002a006"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Ran Raz. 2009. Multi-linear formulas for permanent and determinant are of super-polynomial size. Journal of the ACM 56 2 (2009) Art. 8 17.","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","unstructured":"Ran Raz. 2010. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing 6 (2010) 135\u2013177.","DOI":"10.4086\/toc.2010.v006a007"},{"key":"e_1_3_2_29_2","unstructured":"Ramprasad Saptharishi. 2015. A survey of lower bounds in arithmetic circuit complexity. Github Survey (2015)."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0098246"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Victor Shoup and Roman Smolensky. 1996\/97. Lower bounds for polynomial evaluation and interpolation problems. Computational Complexity 6 4 (1996\/97) 301\u2013311.","DOI":"10.1007\/BF01270384"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","unstructured":"Amir Shpilka and Avi Wigderson. 2001. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10 1 (2001) 1\u201327.","DOI":"10.1007\/PL00001609"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","unstructured":"Amir Shpilka and Amir Yehudayoff. 2009. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends\u00ae in Theoretical Computer Science 5 3-4 (2009) 207\u2013388 (2010).","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520044"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","unstructured":"L. G. Valiant S. Skyum S. Berkowitz and C. Rackoff. 1983. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing 12 4 (1983) 641\u2013644.","DOI":"10.1137\/0212043"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689957","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689957","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:32Z","timestamp":1750295852000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689957"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,11]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3689957"],"URL":"https:\/\/doi.org\/10.1145\/3689957","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,11]]},"assertion":[{"value":"2023-02-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}