{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T09:14:36Z","timestamp":1783502076657,"version":"3.55.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T00:00:00Z","timestamp":1772928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T00:00:00Z","timestamp":1772928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00037-025-00283-6","type":"journal-article","created":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T01:08:58Z","timestamp":1772932138000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Optimal Depth-Reductions for Algebraic Formulas"],"prefix":"10.1007","volume":"35","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guillaume","family":"Malod","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e9bastien","family":"Tavenas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,8]]},"reference":[{"key":"283_CR1","doi-asserted-by":"publisher","unstructured":"Manindra Agrawal & V. Vinay (2008). Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 67\u201375. URL https:\/\/doi.org\/10.1109\/FOCS.2008.32.","DOI":"10.1109\/FOCS.2008.32"},{"key":"283_CR2","doi-asserted-by":"publisher","unstructured":"Maria Luisa Bonet & Samuel R. Buss (1994). Size-depth tradeoffs for Boolean formulae. Information Processing Letters 49(3), 151 \u2013 155. URL https:\/\/doi.org\/10.1016\/0020-0190(94)90093-0.","DOI":"10.1016\/0020-0190(94)90093-0"},{"key":"283_CR3","doi-asserted-by":"publisher","unstructured":"Richard Brent (1974). The Parallel Evaluation of General Arithmetic Expressions. Journal of the ACM 21(2), 201\u2013206. URL https:\/\/doi.org\/10.1145\/321812.32181.","DOI":"10.1145\/321812.32181"},{"key":"283_CR4","doi-asserted-by":"publisher","unstructured":"Richard Brent, Daniel Kuck & Kiyoshi Maruyama (1973). The Parallel Evaluation of Arithmetic Expressions Without Division. IEEE Transactions on Computers C-22(5), 532\u2013534. URL https:\/\/doi.org\/10.1109\/T-C.1973.223757.","DOI":"10.1109\/T-C.1973.223757"},{"key":"283_CR5","doi-asserted-by":"publisher","unstructured":"Peter B\u00fcrgisser (2000). Cook\u2019s versus Valiant\u2019s hypothesis. Theoretical\nComputer Science 235(1), 71\u201388. URL https:\/\/doi.org\/10.1016\/S0304-3975(99)00183-8.","DOI":"10.1016\/S0304-3975(99)00183-8"},{"key":"283_CR6","doi-asserted-by":"publisher","unstructured":"Nader H. Bshouty, Richard Cleve & Wayne Eberly (1995).\nSize-Depth Tradeoffs for Algebraic Formulas. SIAM J. Comput. 24(4),\n682\u2013705. URL https:\/\/doi.org\/10.1137\/S0097539792232586.","DOI":"10.1137\/S0097539792232586"},{"key":"283_CR7","unstructured":"Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi &\nV. Vinay (2016). The Chasm at Depth Four, and Tensor Rank : Old\nresults, new insights. CoRR abs\/1606.04200. URL arXiv:1606.04200."},{"key":"283_CR8","doi-asserted-by":"publisher","unstructured":"Suryajith Chillara, Nutan Limaye & Srikanth Srinivasan\n(2019). Small-depth multilinear formula lower bounds for iterated\nmatrix multiplication with applications. SIAM Journal on Computing\n48(1), 70\u201392. URL https:\/\/doi.org\/10.1137\/18M119156.","DOI":"10.1137\/18M119156"},{"key":"283_CR9","doi-asserted-by":"publisher","unstructured":"Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer,\nGorav Jindal & Vladimir Lysikov (2024). Homogeneous Algebraic\nComplexity Theory and Algebraic Formulas. In 15th Innovations\nin Theoretical Computer Science Conference (ITCS), 43\u20131. URL\nhttps:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.43.","DOI":"10.4230\/LIPIcs.ITCS.2024.43"},{"key":"283_CR10","doi-asserted-by":"publisher","unstructured":"Herv\u00e9 Fournier, Nutan Limaye, Guillaume Malod, Srikanth\nSrinivasan & S\u00e9bastien Tavenas (2023). Towards Optimal Depth-\nReductions for Algebraic Formulas. In 38th Computational Complexity\nConference (CCC 2023), volume 264, pp\u201328. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2023.28.","DOI":"10.4230\/LIPIcs.CCC.2023.28"},{"key":"283_CR11","doi-asserted-by":"publisher","unstructured":"Herv\u00e9 Fournier, Nutan Limaye, Srikanth Srinivasan &\nS\u00e9bastien Tavenas (2024). On the Power of Homogeneous Algebraic\nFormulas. In Proceedings of the 56th Annual ACM Symposium on\nTheory of Computing (STOC), 141\u2013151. URL https:\/\/doi.org\/10.1145\/3618260.3649760.","DOI":"10.1145\/3618260.3649760"},{"key":"283_CR12","doi-asserted-by":"publisher","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad\nSaptharishi (2016). Arithmetic Circuits: A Chasm at Depth 3. SIAM\nJournal of Computing 45(3), 1064\u20131079. URL https:\/\/doi.org\/10.1137\/140957123.","DOI":"10.1137\/140957123"},{"key":"283_CR13","doi-asserted-by":"publisher","unstructured":"Pavel Hrube\u0161 & Amir Yehudayoff (2011). Homogeneous formulas\nand symmetric polynomials. Comput. Complexity 20(3), 559\u2013578. URL\nhttps:\/\/doi.org\/10.1007\/s00037-011-0007-3.","DOI":"10.1007\/s00037-011-0007-3"},{"key":"283_CR14","doi-asserted-by":"publisher","unstructured":"Neeraj Kayal, Chandan Saha & Ramprasad Saptharishi (2014).\nA super-polynomial lower bound for regular arithmetic formulas. In\nProceedings of the forty-sixth annual ACM symposium on Theory\nof computing (STOC), 146\u2013153. URL https:\/\/doi.org\/10.1145\/2591796.2591847.","DOI":"10.1145\/2591796.2591847"},{"key":"283_CR15","doi-asserted-by":"publisher","unstructured":"Pascal Koiran (2012). Arithmetic circuits: The chasm at depth four\ngets wider. Theoretical Computer Science 448, 56\u201365. URL https:\/\/doi.org\/10.1016\/j.tcs.2012.03.041.","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"283_CR16","doi-asserted-by":"publisher","unstructured":"S. Rao Kosaraju (1986). Parallel evaluation of division-free arithmetic\nequations. In Proceedings of the Eighteenth Annual ACM Symposium\non Theory of Computing, 231\u2013239. URL https:\/\/doi.org\/10.1145\/12130.12153.","DOI":"10.1145\/12130.12153"},{"key":"283_CR17","doi-asserted-by":"publisher","unstructured":"Mrinal Kumar, Rafael Mendes de Oliveira & Ramprasad\nSaptharishi (2019). Towards Optimal Depth Reductions for Syntactically\nMultilinear Circuits. In Proceedings of the 46th International\nColloquium on Automata, Languages, and Programming (ICALP), 78\u20131. URL https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.78.","DOI":"10.4230\/LIPIcs.ICALP.2019.78"},{"key":"283_CR18","doi-asserted-by":"publisher","unstructured":"Nutan Limaye, Srikanth Srinivasan & S\u00e9bastien Tavenas\n(2025). Superpolynomial lower bounds against low-depth algebraic circuits.\nJournal of the ACM 72(4), 1\u201335. URL https:\/\/doi.org\/10.1145\/3734215.","DOI":"10.1145\/3734215"},{"key":"283_CR19","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1991). Lower bounds for non-commutative computation.\nIn Proceedings of the twenty-third annual ACM symposium on Theory\nof computing (STOC), 410\u2013418. URL https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/103418.103462.","DOI":"10.1145\/103418.103462"},{"key":"283_CR20","doi-asserted-by":"publisher","unstructured":"Noam Nisan & Avi Wigderson (1997). Lower bounds on arithmetic\ncircuits via partial derivatives. Computational Complexity 6(3), 217\u2013\n234. URL https:\/\/doi.org\/10.1007\/BF01294256.","DOI":"10.1007\/BF01294256"},{"key":"283_CR21","doi-asserted-by":"publisher","unstructured":"Franco P. Preparata & David E. Muller (1975). The Time\nRequired to Evaluate Division-Free Arithmetic Expressions. Information\nProcessing Letters 3(5), 144\u2013146. URL https:\/\/doi.org\/10.1016\/0020-0190(75)90028-9.","DOI":"10.1016\/0020-0190(75)90028-9"},{"key":"283_CR22","doi-asserted-by":"publisher","unstructured":"Franco P. Preparata & David E. Muller (1976). Efficient Parallel\nEvaluation of Boolean Expression. IEEE Transactions on Computers\n25(5), 548\u2013549. URL https:\/\/doi.org\/10.1109\/TC.1976.1674647.","DOI":"10.1109\/TC.1976.1674647"},{"key":"283_CR23","doi-asserted-by":"crossref","unstructured":"Ran Raz (2006). Separation of Multilinear Circuit and Formula\nSize. Theory of Computing 2(1), 121\u2013135. URL https:\/\/theoryofcomputing.org\/articles\/v002a006\/.","DOI":"10.4086\/toc.2006.v002a006"},{"key":"283_CR24","doi-asserted-by":"crossref","unstructured":"Ran Raz (2013). Tensor-Rank and Lower Bounds for Arithmetic Formulas.\nJournal of the ACM 60(6), 40:1\u201340:15. URL http:\/\/doi.acm.org\/10.1145\/2535928.","DOI":"10.1145\/2535928"},{"key":"283_CR25","doi-asserted-by":"publisher","unstructured":"Ran Raz & Amir Yehudayoff (2008). Balancing Syntactically Multilinear\nArithmetic Circuits. Computational Complexity 17(4), 515\u2013535.\nURL https:\/\/doi.org\/10.1007\/s00037-008-0254-0.","DOI":"10.1007\/s00037-008-0254-0"},{"key":"283_CR26","unstructured":"Ramprasad Saptharishi (2015). A survey of lower bounds in\narithmetic circuit complexity. URL https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/. Github survey."},{"key":"283_CR27","doi-asserted-by":"publisher","unstructured":"Eli Shamir & Marc Snir (1980). On the Depth Complexity of Formulas.\nMathematical Systems Theory 13, 301\u2013322. URL https:\/\/doi.org\/10.1007\/BF01744302.","DOI":"10.1007\/BF01744302"},{"key":"283_CR28","doi-asserted-by":"publisher","unstructured":"Amir Shpilka & Avi Wigderson (2001). Depth-3 arithmetic circuits\nover fields of characteristic zero. Computational Complexity 10(1), 1\u2013\n27. URL https:\/\/doi.org\/10.1007\/PL00001609.","DOI":"10.1007\/PL00001609"},{"key":"283_CR29","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A\nsurvey of recent results and open questions. Foundations and Trends in\nTheoretical Computer Science 5, 207\u2013388. URL http:\/\/dx.doi.org\/10.1561\/0400000039.","DOI":"10.1561\/0400000039"},{"key":"283_CR30","unstructured":"Philip M. Spira (1971). On time hardware complexity tradeoffs for\nBoolean functions. In Proceedings of the Fourth Hawaii International\nConference on System Sciences, 525\u2013527."},{"key":"283_CR31","doi-asserted-by":"publisher","unstructured":"S\u00e9bastien Tavenas (2015). Improved bounds for reduction to depth 4\nand depth 3. Information and Computation 240, 2\u201311. URL https:\/\/doi.org\/10.1016\/j.ic.2014.09.004.","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"283_CR32","doi-asserted-by":"publisher","unstructured":"S\u00e9bastien Tavenas, Nutan Limaye & Srikanth Srinivasan\n(2022). Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In Proceedings of the 54th Annual ACM\nSIGACT Symposium on Theory of Computing (STOC), 416\u2013425. URL https:\/\/doi.org\/10.1145\/3519935.3520044.","DOI":"10.1145\/3519935.3520044"},{"key":"283_CR33","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant, Sven Skyum, Stuart J. Berkowitz &\nCharles Rackoff (1983). Fast Parallel Computation of Polynomials\nUsing Few Processors. SIAM Journal of Computing 12(4), 641\u2013644.\nURL https:\/\/doi.org\/10.1137\/0212043.","DOI":"10.1137\/0212043"},{"key":"283_CR34","unstructured":"SV Yablonskii & VP Kozyrev (1968). Mathematical problems of\ncybernetics. Information Materials of Scientific Council of Akad. Nauk\nSSSR on Complex Problem \u201cKibernetika 19, 3\u201315."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00283-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00283-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00283-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T08:28:18Z","timestamp":1783499298000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00283-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,8]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["283"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00283-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,8]]},"assertion":[{"value":"3 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 March 2026","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}