{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T19:15:51Z","timestamp":1789758951461,"version":"4.0.1"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"SERB project","award":["MTR\/2017\/000909"],"award-info":[{"award-number":["MTR\/2017\/000909"]}]},{"name":"Independent Research Fund Denmark","award":["10.46540\/3103-00116B"],"award-info":[{"award-number":["10.46540\/3103-00116B"]}]},{"name":"Basic Algorithms Research Copenhagen (BARC), funded by VILLUM Foundation","award":["16582 and 54451"],"award-info":[{"award-number":["16582 and 54451"]}]},{"name":"BIRCA from the IDEX of Univ. Grenoble Alpes","award":["183459"],"award-info":[{"award-number":["183459"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,8,31]]},"abstract":"\n An Algebraic Circuit for a polynomial\n \n \\(P\\in \\mathbb {F}[x_1,\\ldots ,x_N]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a computational model for constructing the polynomial\n P<\/jats:italic>\n using only additions and multiplications. It is a\n syntactic<\/jats:italic>\n model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over fields other than\n \n \\(\\mathbb {F}_2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ), while constant-depth Boolean circuit lower bounds have been known since the early 1980s.\n <\/jats:p>\n \n In this article, we prove the\n first superpolynomial lower bounds against general algebraic circuits of all constant depths<\/jats:italic>\n over all fields of characteristic 0 (or large). We also prove the first lower bounds against\n homogeneous<\/jats:italic>\n algebraic circuits of constant depth over any field.\n <\/jats:p>\n \n Our approach is surprisingly simple. We first prove superpolynomial lower bounds for constant-depth\n Set-Multilinear<\/jats:italic>\n circuits. While strong lower bounds were already known against such circuits, most previous lower bounds were of the form\n f(d)<\/jats:italic>\n \u22c5 poly(\n N<\/jats:italic>\n ), where\n d<\/jats:italic>\n denotes the degree of the polynomial. In analogy with Parameterized complexity, we call this an\n FPT<\/jats:italic>\n lower bound. We extend a well-known technique of Nisan and Wigderson (FOCS 1995) to prove\n non-FPT<\/jats:italic>\n lower bounds against constant-depth set-multilinear circuits computing the Iterated Matrix Multiplication polynomial IMM\n \n n,d<\/jats:italic>\n <\/jats:sub>\n (which computes a fixed entry of the product of\n d n \u00d7 n<\/jats:italic>\n matrices). More precisely, we prove that any set-multilinear circuit of depth\n \u0394<\/jats:italic>\n computing IMM\n \n n,d<\/jats:italic>\n <\/jats:sub>\n must have size at least\n \n \\(n^{d^{\\exp (-O(\\Delta))}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This result holds over any field, as long as\n d<\/jats:italic>\n =\n o<\/jats:italic>\n (log\n n<\/jats:italic>\n ).\n <\/jats:p>\n \n We then show how to convert any constant-depth algebraic circuit of size\n s<\/jats:italic>\n to a\n constant-depth<\/jats:italic>\n set-multilinear circuit with a blow-up in size that is exponential in\n d<\/jats:italic>\n but only polynomial in\n s<\/jats:italic>\n over fields of characteristic 0. (For depths greater than 3, previous results of this form increased the depth of the resulting circuit to \u03a9 (log\n s<\/jats:italic>\n ).) This implies our constant-depth circuit lower bounds.\n <\/jats:p>\n \n We can also use these lower bounds to prove a Depth Hierarchy theorem for constant-depth circuits. We show that for every depth\n \u0393<\/jats:italic>\n , there is an explicit polynomial which can be computed by a depth\n \u0393<\/jats:italic>\n circuit of size\n s<\/jats:italic>\n , but requires circuits of size\n s<\/jats:italic>\n \u03c9 (1)<\/jats:sup>\n if the depth is \u0393 -1.\n <\/jats:p>\n Finally, we observe that our superpolynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small depth circuits using the known connection between algebraic hardness and randomness.<\/jats:p>","DOI":"10.1145\/3734215","type":"journal-article","created":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T07:08:33Z","timestamp":1748848113000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0238-1674","authenticated-orcid":false,"given":"Nutan","family":"Limaye","sequence":"first","affiliation":[{"name":"Computer Science, IT-Universitet i K\u00f8benhavn","place":["Kobenhavn, Denmark"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6491-124X","authenticated-orcid":false,"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Computer Science, K\u00f8benhavns Universitet","place":["Copenhagen, Denmark"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0025-0005","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Tavenas","sequence":"additional","affiliation":[{"name":"CNRS, LAMA, Universit\u00e9 Savoie Mont Blanc","place":["Chamb\u00e9ry, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,7,24]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_4_3_2","first-page":"389","volume-title":"Proceedings of the STOC","author":"Andrews Robert","year":"2022","unstructured":"Robert Andrews and Michael A. Forbes. 2022. Ideals, determinants, and straightening: Proving and using lower bounds for polynomial ideals. In Proceedings of the STOC. ACM, 389\u2013402."},{"key":"e_1_3_4_4_2","first-page":"87","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"Beame Paul","year":"2010","unstructured":"Paul Beame, Trinh Huynh, and Toniann Pitassi. 2010. Hardness amplification in proof complexity. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Leonard J. Schulman (Ed.). ACM, 87\u201396."},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.ic.2012.10.004","article-title":"Algebraic independence and blackbox identity testing","volume":"222","author":"Beecken Malte","year":"2013","unstructured":"Malte Beecken, Johannes Mittmann, and Nitin Saxena. 2013. Algebraic independence and blackbox identity testing. Information and Computation 222 (2013), 2\u201319.","journal-title":"Information and Computation"},{"key":"e_1_3_4_6_2","series-title":"LIPIcs","first-page":"183","volume-title":"Proceedings of the Conference on Computational Complexity","volume":"33","author":"Bera Suman K.","year":"2015","unstructured":"Suman K. Bera and Amit Chakrabarti. 2015. A depth-five lower bound for iterated matrix multiplication. In Proceedings of the Conference on Computational Complexity(LIPIcs, Vol. 33). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 183\u2013197."},{"key":"e_1_3_4_7_2","series-title":"LIPIcs","first-page":"18:1\u201318:16","volume-title":"Proceedings of the MFCS","volume":"241","author":"Bhargav C. S.","year":"2022","unstructured":"C. S. Bhargav, Sagnik Dutta, and Nitin Saxena. 2022. Improved lower bound, and proof barrier, for constant depth algebraic circuits. In Proceedings of the MFCS(LIPIcs, Vol. 241). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:16."},{"issue":"1","key":"e_1_3_4_8_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0304-3975(99)00183-8","article-title":"Cook\u2019s versus Valiant\u2019s hypothesis","volume":"235","author":"B\u00fcrgisser Peter","year":"2000","unstructured":"Peter B\u00fcrgisser. 2000. Cook\u2019s versus Valiant\u2019s hypothesis. Theoretical Computer Science 235, 1 (2000), 71\u201388.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_4_9_2","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"B\u00fcrgisser Peter","year":"1997","unstructured":"Peter B\u00fcrgisser, Michael Clausen, and Mohammad Amin Shokrollahi. 1997. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, Vol. 315. Springer."},{"key":"e_1_3_4_10_2","first-page":"166","article-title":"Lower bounds for monotone arithmetic circuits via communication complexity","volume":"27","author":"Chattopadhyay Arkadev","year":"2020","unstructured":"Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. 2020. Lower bounds for monotone arithmetic circuits via communication complexity. Electron. Colloquium Comput. Complex. (To appear in CCC 2021) 27 (2020), 166.","journal-title":"Electron. Colloquium Comput. Complex. (To appear in CCC 2021)"},{"key":"e_1_3_4_11_2","first-page":"191","article-title":"Negations provide strongly exponential savings","volume":"27","author":"Chattopadhyay Arkadev","year":"2020","unstructured":"Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. 2020. Negations provide strongly exponential savings. Electron. Colloquium Comput. Complex. 27 (2020), 191.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_4_12_2","first-page":"066","article-title":"A near-optimal depth-hierarchy theorem for small-depth multilinear circuits","volume":"25","author":"Chillara Suryajith","year":"2018","unstructured":"Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. 2018. A near-optimal depth-hierarchy theorem for small-depth multilinear circuits. Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 066. Retrieved from https:\/\/eccc.weizmann.ac.il\/report\/2018\/066\/s","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_4_13_2","article-title":"The chasm at depth four, and tensor rank: Old results, new insights","author":"Chillara Suryajith","year":"2016","unstructured":"Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, and V. Vinay. 2016. The chasm at depth four, and tensor rank: Old results, new insights. CoRR arXiv:1606.04200. Retrieved from https:\/\/arxiv.org\/abs\/1606.04200. (2016).","journal-title":"CoRR"},{"key":"e_1_3_4_14_2","article-title":"Some closure results for polynomial factorization and applications","author":"Chou Chi-Ning","year":"2018","unstructured":"Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. 2018. Some closure results for polynomial factorization and applications. CoRR arXiv:1803.05933. Retrieved from https:\/\/arxiv.org\/abs\/1803.05933. (2018).","journal-title":"CoRR"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a013"},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer Publishing Company, Incorporated."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214034"},{"issue":"4","key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1137\/080735850","article-title":"Hardness-randomness tradeoffs for bounded depth arithmetic circuits","volume":"39","author":"Dvir Zeev","year":"2009","unstructured":"Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. 2009. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing 39, 4 (2009), 1279\u20131293.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"e_1_3_4_19_2","doi-asserted-by":"crossref","first-page":"1173","DOI":"10.1137\/140990280","article-title":"Lower bounds for depth-4 formulas computing iterated matrix multiplication","volume":"44","author":"Fournier Herv\u00e9","year":"2015","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.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/978-3-319-62389-4_21","volume-title":"Proceedings of the International Computing and Combinatorics Conference","author":"Ghosal Purnata","year":"2017","unstructured":"Purnata Ghosal, Om Prakash, and BV Raghavendra Rao. 2017. On constant depth circuits parameterized by degree: Identity testing and depth reduction. In Proceedings of the International Computing and Combinatorics Conference. Springer, 250\u2013261."},{"issue":"1","key":"e_1_3_4_22_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.3233\/FI-2020-1980","article-title":"On proving parameterized size lower bounds for multilinear algebraic models","volume":"177","author":"Ghosal Purnata","year":"2020","unstructured":"Purnata Ghosal and B. V. Raghavendra Rao. 2020. On proving parameterized size lower bounds for multilinear algebraic models. Fundamenta Informaticae 177, 1 (2020), 69\u201393.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_3_4_23_2","first-page":"188","volume-title":"Proceedings of the FOCS","author":"Govindasamy Nashlen","year":"2022","unstructured":"Nashlen Govindasamy, Tuomas Hakoniemi, and Iddo Tzameret. 2022. Simple hard instances for low-depth algebraic proofs. In Proceedings of the FOCS. IEEE, 188\u2013199."},{"issue":"6","key":"e_1_3_4_24_2","first-page":"37:1\u201337:59","article-title":"Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system","volume":"65","author":"Grochow Joshua A.","year":"2018","unstructured":"Joshua A. Grochow and Toniann Pitassi. 2018. Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. Journal of the ACM 65, 6 (2018), 37:1\u201337:59.","journal-title":"Journal of the ACM"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/140957123"},{"key":"e_1_3_4_27_2","series-title":"LIPIcs","first-page":"23:1\u201323:31","volume-title":"Proceedings of the 35th Computational Complexity Conference, CCC 2020, July 28\u201331, 2020, Saarbr\u00fccken, Germany (Virtual 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, CCC 2020, July 28\u201331, 2020, Saarbr\u00fccken, Germany (Virtual Conference)(LIPIcs, Vol. 169). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 23:1\u201323:31."},{"issue":"1","key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","article-title":"Asymptotic formula\u00e6 in combinatory analysis","volume":"2","author":"Hardy Godfrey H.","year":"1918","unstructured":"Godfrey H. Hardy and Srinivasa Ramanujan. 1918. Asymptotic formula\u00e6 in combinatory analysis. Proceedings of the London Mathematical Society 2, 1 (1918), 75\u2013115.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"e_1_3_4_29_2","series-title":"STOC \u201986","first-page":"6","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"Hastad J.","year":"1986","unstructured":"J. Hastad. 1986. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (Berkeley, California, USA) (STOC \u201986). Association for Computing Machinery, New York, NY, USA, 6\u201320. DOI:10.1145\/12130.12132"},{"key":"e_1_3_4_30_2","volume-title":"Computational Limitations of Small-depth Circuits","author":"H\u00e5stad J.","year":"1987","unstructured":"J. H\u00e5stad. 1987. Computational Limitations of Small-depth Circuits. MIT Press. lc86033802 Retrieved from https:\/\/books.google.co.in\/books?id=_h0ZAQAAIAAJ"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3095799"},{"issue":"1","key":"e_1_3_4_32_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ipl.2009.09.003","article-title":"Monotone separations for constant degree polynomials","volume":"110","author":"Hrube\u0161 Pavel","year":"2009","unstructured":"Pavel Hrube\u0161 and Amir Yehudayoff. 2009. Monotone separations for constant degree polynomials. Information Processing Letters 110, 1 (2009), 1\u20133.","journal-title":"Information Processing Letters"},{"issue":"3","key":"e_1_3_4_33_2","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/s00037-011-0007-3","article-title":"Homogeneous formulas and symmetric polynomials","volume":"20","author":"Hrube\u0161 Pavel","year":"2011","unstructured":"Pavel Hrube\u0161 and Amir Yehudayoff. 2011. Homogeneous formulas and symmetric polynomials. Computational Complexity 20, 3 (2011), 559\u2013578.","journal-title":"Computational Complexity"},{"issue":"3","key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/s00037-011-0007-3","article-title":"Homogeneous formulas and symmetric polynomials","volume":"20","author":"Hrube\u0161 Pavel","year":"2011","unstructured":"Pavel Hrube\u0161 and Amir Yehudayoff. 2011. Homogeneous formulas and symmetric polynomials. Computational Complexity 20, 3 (2011), 559\u2013578.","journal-title":"Computational Complexity"},{"issue":"3","key":"e_1_3_4_35_2","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1145\/322326.322341","article-title":"Some exact complexity results for straight-line computations over semirings","volume":"29","author":"Jerrum Mark","year":"1982","unstructured":"Mark Jerrum and Marc Snir. 1982. Some exact complexity results for straight-line computations over semirings. J. ACM 29, 3 (1982), 874\u2013897.","journal-title":"J. ACM"},{"issue":"1","key":"e_1_3_4_36_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","article-title":"Derandomizing polynomial identity tests means proving circuit lower bounds","volume":"13","author":"Kabanets Valentine","year":"2004","unstructured":"Valentine Kabanets and Russell Impagliazzo. 2004. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13, 1\u20132 (2004), 1\u201346.","journal-title":"Computational Complexity"},{"issue":"6","key":"e_1_3_4_37_2","doi-asserted-by":"crossref","first-page":"2114","DOI":"10.1137\/110824516","article-title":"Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in","volume":"42","author":"Karnin Zohar Shay","year":"2013","unstructured":"Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. 2013. Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM Journal on Computing 42, 6 (2013), 2114\u20132131.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_38_2","first-page":"81","article-title":"An exponential lower bound for the sum of powers of bounded degree polynomials","volume":"19","author":"Kayal Neeraj","year":"2012","unstructured":"Neeraj Kayal. 2012. An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloquium Comput. Complex. 19 (2012), 81. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2012\/081","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_4_39_2","first-page":"119","volume-title":"Proceedings of the Symposium on Theory of Computing, STOC 2014, New York, USA","author":"Kayal Neeraj","year":"2014","unstructured":"Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. 2014. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In Proceedings of the Symposium on Theory of Computing, STOC 2014, New York, USA, David B. Shmoys (Ed.). ACM, 119\u2013127."},{"issue":"1","key":"e_1_3_4_40_2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1137\/151002423","article-title":"An exponential lower bound for homogeneous depth four arithmetic formulas","volume":"46","author":"Kayal Neeraj","year":"2017","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.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"e_1_3_4_41_2","first-page":"2","article-title":"Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits","volume":"12","author":"Kayal Neeraj","year":"2020","unstructured":"Neeraj Kayal, Vineet Nair, and Chandan Saha. 2020. Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits. ACM Transactions on Computation Theory 12, 1, Article 2 (Feb.2020), 27 pages.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_4_42_2","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"33:1\u201333:15","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","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 (ICALP\u201916)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 55). 33:1\u201333:15."},{"issue":"16","key":"e_1_3_4_43_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2018.v014a016","article-title":"On the size of homogeneous and of depth-four formulas with low individual degree","volume":"14","author":"Kayal Neeraj","year":"2018","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, 16 (2018), 1\u201346.","journal-title":"Theory Of Computing"},{"issue":"1","key":"e_1_3_4_44_2","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/18M1173319","article-title":"The computational power of depth five arithmetic circuits","volume":"48","author":"Kumar Mrinal","year":"2019","unstructured":"Mrinal Kumar and Ramprasad Saptharishi. 2019. The computational power of depth five arithmetic circuits. SIAM Journal on Computing 48, 1 (2019), 144\u2013180.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_45_2","article-title":"Hardness-randomness tradeoffs for algebraic computation","volume":"129","author":"Kumar Mrinal","year":"2019","unstructured":"Mrinal Kumar and Ramprasad Saptharishi. 2019. Hardness-randomness tradeoffs for algebraic computation. Bulletin of the EATCS 129 (2019).","journal-title":"Bulletin of the EATCS"},{"issue":"1","key":"e_1_3_4_46_2","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1137\/140999335","article-title":"On the power of homogeneous depth 4 arithmetic circuits","volume":"46","author":"Kumar Mrinal","year":"2017","unstructured":"Mrinal Kumar and Shubhangi Saraf. 2017. On the power of homogeneous depth 4 arithmetic circuits. SIAM Journal on Computing 46, 1 (2017), 336\u2013387.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_47_2","series-title":"LIPIcs","first-page":"32:1\u201332:23","volume-title":"Proceedings of the CCC","volume":"234","author":"Limaye Nutan","year":"2022","unstructured":"Nutan Limaye, Srikanth Srinivasan, and S\u00e9bastien Tavenas. 2022. On the partial derivative method applied to lopsided set-multilinear polynomials. In Proceedings of the CCC(LIPIcs, Vol. 234). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1\u201332:23."},{"key":"e_1_3_4_48_2","volume-title":"Symmetric Functions and Hall Polynomials","author":"Macdonald Ian Grant","year":"1998","unstructured":"Ian Grant Macdonald. 1998. Symmetric Functions and Hall Polynomials. Oxford university press."},{"issue":"6","key":"e_1_3_4_49_2","doi-asserted-by":"crossref","first-page":"1577","DOI":"10.1016\/j.disc.2019.02.013","article-title":"Combinatorial proofs of the Newton\u2013Girard and Chapman\u2013Costas-Santos identities","volume":"342","author":"Mukherjee Sajal Kumar","year":"2019","unstructured":"Sajal Kumar Mukherjee and Sudip Bera. 2019. Combinatorial proofs of the Newton\u2013Girard and Chapman\u2013Costas-Santos identities. Discrete Mathematics 342, 6 (2019), 1577\u20131580.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_4_50_2","first-page":"410","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing","author":"Nisan Noam","year":"1991","unstructured":"Noam Nisan. 1991. Lower bounds for non-commutative computation. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. 410\u2013418."},{"issue":"2","key":"e_1_3_4_51_2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","article-title":"Hardness vs randomness","volume":"49","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan and Avi Wigderson. 1994. Hardness vs randomness. Journal of Computer and System Sciences 49, 2 (1994), 149\u2013167.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_3_4_53_2","series-title":"LIPIcs","first-page":"8:1\u20138:33","volume-title":"Proceedings of the 35th Computational Complexity Conference, CCC 2020, July 28\u201331, 2020, Saarbr\u00fccken, Germany (Virtual Conference)","volume":"169","author":"Peleg Shir","year":"2020","unstructured":"Shir Peleg and Amir Shpilka. 2020. A generalized sylvester-gallai type theorem for quadratic polynomials. In Proceedings of the 35th Computational Complexity Conference, CCC 2020, July 28\u201331, 2020, Saarbr\u00fccken, Germany (Virtual Conference)(LIPIcs, Vol. 169), Shubhangi Saraf (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 8:1\u20138:33."},{"key":"e_1_3_4_54_2","article-title":"Polynomial time deterministic identity testingalgorithm for \\(\\Sigma\\) \\({}^{\\mbox{[3]}}\\) \\(\\Pi\\) \\(\\Sigma\\) \\(\\Pi\\) \\({}^{\\mbox{[2]}}\\) circuits via Edelstein-Kelly type theorem for quadratic polynomials","author":"Peleg Shir","year":"2020","unstructured":"Shir Peleg and Amir Shpilka. 2020. Polynomial time deterministic identity testingalgorithm for \\(\\Sigma\\) \\({}^{\\mbox{[3]}}\\) \\(\\Pi\\) \\(\\Sigma\\) \\(\\Pi\\) \\({}^{\\mbox{[2]}}\\) circuits via Edelstein-Kelly type theorem for quadratic polynomials. CoRR (to Appear in STOC 2021) arXiv:2006.08263. Retrieved from https:\/\/arxiv.org\/abs\/2006.08263. (2020).","journal-title":"CoRR (to Appear in STOC 2021)"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a007"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535928"},{"issue":"3","key":"e_1_3_4_58_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s004930050062","article-title":"Separation of the monotone NC hierarchy","volume":"19","author":"Raz Ran","year":"1999","unstructured":"Ran Raz and Pierre McKenzie. 1999. Separation of the monotone NC hierarchy. Combinatorica 19, 3 (1999), 403\u2013435.","journal-title":"Combinatorica"},{"issue":"2","key":"e_1_3_4_59_2","first-page":"598","article-title":"Lower bounds on the size of constant-depth networks over a complete basis with logical addition.","volume":"41","author":"Razborov Alexander A.","year":"1986","unstructured":"Alexander A. Razborov. 1986. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki 41, 2 (1986), 598\u2013607.","journal-title":"Mathematicheskie Zametki"},{"issue":"5","key":"e_1_3_4_60_2","doi-asserted-by":"crossref","first-page":"1986","DOI":"10.1137\/15M1027310","article-title":"Formulas versus circuits for small distance connectivity","volume":"47","author":"Rossman Benjamin","year":"2018","unstructured":"Benjamin Rossman. 2018. Formulas versus circuits for small distance connectivity. SIAM Journal on Computing 47, 5 (2018), 1986\u20132028.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_61_2","unstructured":"Ramprasad Saptharishi. 2015. A Survey of Lower Bounds in Arithmetic Circuit Complexity. (2015). Retrieved from https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/. Github survey."},{"issue":"5","key":"e_1_3_4_62_2","doi-asserted-by":"crossref","first-page":"1205","DOI":"10.1007\/s00493-016-3460-4","article-title":"Black-box identity testing of depth-4 multilinear circuits","volume":"38","author":"Saraf Shubhangi","year":"2018","unstructured":"Shubhangi Saraf and Ilya Volkovich. 2018. Black-box identity testing of depth-4 multilinear circuits. Combinatorica 38, 5 (2018), 1205\u20131238.","journal-title":"Combinatorica"},{"issue":"5","key":"e_1_3_4_63_2","doi-asserted-by":"crossref","first-page":"1285","DOI":"10.1137\/10848232","article-title":"Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn\u2019t matter","volume":"41","author":"Saxena Nitin","year":"2012","unstructured":"Nitin Saxena and Comandur Seshadhri. 2012. Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn\u2019t matter. SIAM Journal on Computing 41, 5 (2012), 1285\u20131298.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_4_64_2","volume-title":"Diophantine Approximations and Diophantine Equations","author":"Schmidt Wolfgang M.","year":"2006","unstructured":"Wolfgang M. Schmidt. 2006. Diophantine Approximations and Diophantine Equations. Springer."},{"key":"e_1_3_4_65_2","article-title":"Lower bounds on the number of multiplications and the number of additions in monotone computations","author":"Shamir Eli","year":"1977","unstructured":"Eli Shamir and Marc Snir. 1977. Lower bounds on the number of multiplications and the number of additions in monotone computations. IBM Thomas J. Watson Research Division (1977).","journal-title":"IBM Thomas J. Watson Research Division"},{"key":"e_1_3_4_66_2","article-title":"An improved lower bound for depth four arithmetic circuits","author":"Sharma Abhijat","year":"2017","unstructured":"Abhijat Sharma. 2017. An improved lower bound for depth four arithmetic circuits. Master\u2019s Thesis, Indian Institute of Science, Bangalore, India. (2017).","journal-title":"Master\u2019s Thesis, Indian Institute of Science, Bangalore, India."},{"issue":"4","key":"e_1_3_4_67_2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01270384","article-title":"Lower bounds for polynomial evaluation and interpolation problems","volume":"6","author":"Shoup Victor","year":"1996","unstructured":"Victor Shoup and Roman Smolensky. 1996. Lower bounds for polynomial evaluation and interpolation problems. Computational Complexity 6, 4 (1996), 301\u2013311.","journal-title":"Computational Complexity"},{"issue":"1","key":"e_1_3_4_68_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00001609","article-title":"Depth-3 arithmetic circuits over fields of characteristic zero","volume":"10","author":"Shpilka Amir","year":"2001","unstructured":"Amir Shpilka and Avi Wigderson. 2001. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10, 1 (2001), 1\u201327.","journal-title":"Computational Complexity"},{"key":"e_1_3_4_69_2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1561\/0400000039","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 3\u20134 (March2010), 207\u2013388.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_4_70_2","first-page":"77","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC\u201987)","author":"Smolensky Roman","year":"1987","unstructured":"Roman Smolensky. 1987. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC\u201987). Association for Computing Machinery, New York, NY, USA, 77\u201382. DOI:10.1145\/28395.28404"},{"key":"e_1_3_4_71_2","first-page":"184","article-title":"Vermeidung von divisionen.","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen. 1973. Vermeidung von divisionen. Journal f\u00fcr die reine und angewandte Mathematik 264 (1973), 184\u2013202. Retrieved from http:\/\/eudml.org\/doc\/151394","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_3_4_72_2","first-page":"416","volume-title":"Proceedings of the STOC","author":"Tavenas S\u00e9bastien","year":"2022","unstructured":"S\u00e9bastien Tavenas, Nutan Limaye, and Srikanth Srinivasan. 2022. Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In Proceedings of the STOC. ACM, 416\u2013425."},{"issue":"3","key":"e_1_3_4_73_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(80)90060-2","article-title":"Negation can be exponentially powerful","volume":"12","author":"Valiant Leslie G.","year":"1980","unstructured":"Leslie G. Valiant. 1980. Negation can be exponentially powerful. Theoretical Computer Science 12, 3 (1980), 303\u2013314.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_4_74_2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/3-540-55808-X_10","volume-title":"Proceedings of the Mathematical Foundations of Computer Science 1992","author":"Wigderson Avi","year":"1992","unstructured":"Avi Wigderson. 1992. The complexity of graph connectivity. In Proceedings of the Mathematical Foundations of Computer Science 1992, Ivan M. Havel and V\u00e1clav Koubek (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 112\u2013132."},{"key":"e_1_3_4_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_3_4_76_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90192-X"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3734215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T13:52:20Z","timestamp":1753365140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3734215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,24]]},"references-count":75,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1145\/3734215"],"URL":"https:\/\/doi.org\/10.1145\/3734215","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,24]]},"assertion":[{"value":"2022-02-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}