{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T05:35:11Z","timestamp":1771911311831,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00037-022-00223-8","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T02:03:02Z","timestamp":1656986582000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Quadratic Lower Bounds for Algebraic Branching Programs and Formulas"],"prefix":"10.1007","volume":"31","author":[{"given":"Prerona","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"She","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben","family":"Lee Volk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"223_CR1","doi-asserted-by":"crossref","unstructured":"Walter Baur & Volker Strassen. (1983). The Complexity of Partial Derivatives. Theoretical Computer Science, 22, 317\u2013330.","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"223_CR2","doi-asserted-by":"crossref","unstructured":"Michael Ben-Or (1983). Lower Bounds for Algebraic Computation Trees (Preliminary Report). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing,25-27 April, 1983, Boston, Massachusetts, USA, David\u00a0S. Johnson, Ronald Fagin, Michael\u00a0L. Fredman, David Harel, Richard\u00a0M. Karp, Nancy\u00a0A. Lynch, Christos\u00a0H. Papadimitriou, Ronald\u00a0L. Rivest, Walter\u00a0L. Ruzzo & Joel\u00a0I. Seiferas, editors, 80\u201386. ACM. URL https:\/\/doi.org\/10.1145\/800061.808735.","DOI":"10.1145\/800061.808735"},{"key":"223_CR3","doi-asserted-by":"crossref","unstructured":"Michael Ben-Or (1994). Algebraic Computation Trees in Characteristic p > 0 (Extended Abstract). In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, 534\u2013539. IEEE Computer Society. URL https:\/\/doi.org\/10.1109\/SFCS.1994.365738.","DOI":"10.1109\/SFCS.1994.365738"},{"key":"223_CR4","doi-asserted-by":"crossref","unstructured":"Jin-yi Cai, Xi\u00a0Chen & Dong Li (2010). Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. Comput. Complex. 19(1), 37\u201356. URL https:\/\/doi.org\/10.1007\/s00037-009-0284-2.","DOI":"10.1007\/s00037-009-0284-2"},{"key":"223_CR5","unstructured":"Prerona Chatterjee, Mrinal Kumar, Adrian She & Ben\u00a0Lee Volk (2020). A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbr\u00fccken, Germany (Virtual Conference), Shubhangi Saraf, editor, volume 169 of LIPIcs, 2:1\u20132:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2020.2."},{"key":"223_CR6","unstructured":"David\u00a0A. Cox, John\u00a0B. Little & Donal O'Shea (2007). Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer."},{"key":"223_CR7","doi-asserted-by":"crossref","unstructured":"Zeev Dvir, Guillaume Malod, Sylvain Perifel & Amir Yehudayoff (2012). Separating multilinear branching programs and formulas. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, Howard\u00a0J. Karloff & Toniann Pitassi, editors, 615\u2013624. ACM. URL https:\/\/doi.org\/10.1145\/2213977.2214034.","DOI":"10.1145\/2213977.2214034"},{"key":"223_CR8","doi-asserted-by":"crossref","unstructured":"Paul Erd\u0151s, Ronald\u00a0L. Graham & Endre Szemer\u00e9di (1975). On sparse graphs with dense long paths. Computers & Mathematics with Applications 1(3), 365 \u2013 369. ISSN 0898-1221. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/0898122175900371.","DOI":"10.1016\/0898-1221(75)90037-1"},{"key":"223_CR9","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2016). Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput. 45(3), 1064\u20131079. URL https:\/\/doi.org\/10.1137\/140957123.","DOI":"10.1137\/140957123"},{"key":"223_CR10","unstructured":"Pavel Hrubes & Amir Yehudayoff (2016). On Isoperimetric Profiles and Computational Complexity. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani & Davide Sangiorgi, editors, volume\u00a055 of LIPIcs, 89:1\u201389:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.89."},{"key":"223_CR11","doi-asserted-by":"crossref","unstructured":"Stasys Jukna (2012). Boolean function complexity: advances and frontiers, volume\u00a027. Springer Science & Business Media.","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"3","key":"223_CR12","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/0214050","volume":"14","author":"Kyriakos Kalorkoti","year":"1985","unstructured":"Kalorkoti, Kyriakos. (1985). A Lower Bound for the Formula Size of Rational Functions. SIAM Journal on Computing, 14(3), 678\u2013687.","journal-title":"SIAM Journal on Computing"},{"key":"223_CR13","doi-asserted-by":"crossref","unstructured":"Mauricio Karchmer & Avi Wigderson (1993). On Span Programs. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, 102\u2013111. IEEE Computer Society. URL https:\/\/doi.org\/10.1109\/SCT.1993.336536.","DOI":"10.1109\/SCT.1993.336536"},{"key":"223_CR14","doi-asserted-by":"crossref","unstructured":"Mrinal Kumar (2019). A quadratic lower bound for homogeneous algebraic branching programs. Computational Complexity 28(3), 409\u2013435. URL https:\/\/doi.org\/10.1007\/s00037-019-00186-3.","DOI":"10.1007\/s00037-019-00186-3"},{"key":"223_CR15","unstructured":"Nutan Limaye, Kunal Mittal & Mukesh Pareek (2019). Homogeneous ABP complexity of elementary symmetric polynomial. Personal Communication. URL https:\/\/www.cse.iitb.ac.in\/~nutan\/papers\/abp-complexity.pdf."},{"key":"223_CR16","unstructured":"Meena Mahajan & V.\u00a0Vinay (1997). Determinant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sci. 1997. URL http:\/\/cjtcs.cs.uchicago.edu\/articles\/1997\/5\/contents.html."},{"key":"223_CR17","unstructured":"Izaak Meckler & Gjergji Zaimi (2017). Singular locus of zero locus of elementary symmetric polynomials. URL https:\/\/mathoverflow.net\/questions\/264226\/singular-locus-of-zero-set-of-elementary-symmetric-polynomial."},{"issue":"79","key":"223_CR18","doi-asserted-by":"publisher","first-page":"4241","DOI":"10.1155\/S1073792804142566","volume":"2004","author":"Thierry Mignon & Nicolas Ressayre","year":"2004","unstructured":"Thierry Mignon & Nicolas Ressayre. (2004). A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices, 2004(79), 4241\u20134253.","journal-title":"International Mathematics Research Notices"},{"key":"223_CR19","unstructured":"Eduard\u00a0Ivanovich Nechiporuk (1966). On a Boolean function. Dokl. Akad. Nauk SSSR 169, 765\u2013766. URL http:\/\/mi.mathnet.ru\/dan32449."},{"key":"223_CR20","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1991). Lower Bounds for Non-Commutative Computation (Extended Abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, Cris Koutsougeras & Jeffrey\u00a0Scott Vitter, editors, 410\u2013418. ACM. URL https:\/\/doi.org\/10.1145\/103418.103462.","DOI":"10.1145\/103418.103462"},{"key":"223_CR21","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1997). Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity 6(3), 217\u2013234. Available on citeseer:10.1.1.90.2644.","DOI":"10.1007\/BF01294256"},{"key":"223_CR22","doi-asserted-by":"crossref","unstructured":"Ran Raz (2006). Separation of Multilinear Circuit and Formula Size. Theory of Computing 2(6), 121\u2013135. URL https:\/\/doi.org\/10.4086\/toc.2006.v002a006.","DOI":"10.4086\/toc.2006.v002a006"},{"issue":"4","key":"223_CR23","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s00037-008-0254-0","volume":"17","author":"Ran Raz & Amir Yehudayoff","year":"2008","unstructured":"Ran Raz & Amir Yehudayoff. (2008). Balancing Syntactically Multilinear Arithmetic Circuits. Computational Complexity, 17(4), 515\u2013535.","journal-title":"Computational Complexity"},{"key":"223_CR24","unstructured":"Ramprasad Saptharishi (2015). A survey of lower bounds in arithmetic circuit complexity. URL https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/. GitHub survey."},{"key":"223_CR25","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Avi Wigderson (2001). Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. 10(1), 1\u201327. URL https:\/\/doi.org\/10.1007\/PL00001609.","DOI":"10.1007\/PL00001609"},{"key":"223_CR26","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3-4), 207\u2013388. URL https:\/\/doi.org\/10.1561\/0400000039.","DOI":"10.1561\/0400000039"},{"key":"223_CR27","unstructured":"Justin\u00a0R. Smith (2014). Introduction to Algebraic Geometry. Textbooks in Mathematics. Taylor & Francis. ISBN 9781466572485. URL https:\/\/books.google.com\/books?id=zx7usgEACAAJ."},{"key":"223_CR28","doi-asserted-by":"crossref","unstructured":"Roman Smolensky (1997). Easy Lower Bound for a Strange Computational Model. Computational Complexity 6(3), 213\u2013216. URL https:\/\/doi.org\/10.1007\/BF01294255.","DOI":"10.1007\/BF01294255"},{"key":"223_CR29","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1973a). Die Berechnungskomplexit\u00e4t Von Elementarsymmetrischen Funktionen Und Von Interpolationskoeffizienten. Numerische Mathematik 20(3), 238\u2013251. ISSN 0029-599X. URL http:\/\/dx.doi.org\/10.1007\/BF01436566.","DOI":"10.1007\/BF01436566"},{"key":"223_CR30","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1973). Vermeidung von Divisionen. Journal f\u00fcr die reine und angewandte Mathematik 264, 184\u2013202. URL http:\/\/eudml.org\/doc\/151394.","DOI":"10.1515\/crll.1973.264.184"},{"key":"223_CR31","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G. Valiant (1977). Graph-Theoretic Arguments in Low-Level Complexity. In Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings, Jozef Gruska, editor, volume\u00a053 of Lecture Notes in Computer Science, 162\u2013176. Springer. URL https:\/\/doi.org\/10.1007\/3-540-08353-7_135.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"223_CR32","unstructured":"Akihiro Yabe (2015). Bi-polynomial rank and determinantal complexity. CoRR. arXiv: 1504.00151."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00223-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00223-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00223-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T15:26:56Z","timestamp":1669303616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00223-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["223"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00223-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"2 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}