{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:18Z","timestamp":1787017398649,"version":"build-2736575974"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T00:00:00Z","timestamp":1706140800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"IDEX of Univ. Grenoble Alpes","award":["183459"],"award-info":[{"award-number":["183459"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>\n                    An Algebraic Circuit for a multivariate polynomial\n                    <jats:italic>P<\/jats:italic>\n                    is a computational model for constructing the polynomial\n                    <jats:italic>P<\/jats:italic>\n                    using only additions and multiplications. It is a\n                    <jats:italic>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 any field other than F\n                    <jats:sub>2<\/jats:sub>\n                    ), while constant-depth Boolean circuit lower bounds have been known since the early 1980s.\n                  <\/jats:p>\n                  <jats:p>\n                    In this paper, we prove the\n                    <jats:italic>first superpolynomial lower bounds against algebraic circuits of all constant depths<\/jats:italic>\n                    over all fields of characteristic 0. We also observe that our super-polynomial 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.\n                  <\/jats:p>","DOI":"10.1145\/3611094","type":"journal-article","created":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T11:39:18Z","timestamp":1706182758000},"page":"101-108","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":"67","author":[{"given":"Nutan","family":"Limaye","sequence":"first","affiliation":[{"name":"ITU Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e9bastien","family":"Tavenas","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Savoie Mont Blanc, CNRS, LAMA, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806703"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Theor","volume":"235","author":"B\u00fcrgisser P.","year":"2000","unstructured":"B\u00fcrgisser, P. Cook's versus valiant's hypothesis. Theor. Comput. Sci. 235, 1 (2000), 71--88.","journal-title":"Comput. Sci."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_5_1","volume-title":"Closure results for polynomial factorization. Theory Comput. 15: Paper No. 13, 34","author":"Chou C.-N.","year":"2019","unstructured":"Chou, C.-N., Kumar, M., Solomon, N. Closure results for polynomial factorization. Theory Comput. 15: Paper No. 13, 34 (2019)."},{"key":"e_1_2_1_6_1","first-page":"4","article-title":"Hardness-randomness tradeoffs for bounded depth arithmetic circuits","volume":"39","author":"Dvir Z.","year":"2009","unstructured":"Dvir, Z., Shpilka, A., Yehudayoff, A. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput. 39, 4 (2009), 1279--1293.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990280"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957123"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0007-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_13_1","first-page":"129","article-title":"Hardness-randomness tradeoffs for algebraic computation","author":"Kumar M.","year":"2019","unstructured":"Kumar, M., Saptharishi, R. Hardness-randomness tradeoffs for algebraic computation. Bull. EATCS 129 (2019).","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/140999335"},{"key":"e_1_2_1_15_1","first-page":"3","article-title":"Lower bounds on arithmetic circuits via partial derivatives","volume":"6","author":"Nisan N.","year":"1997","unstructured":"Nisan, N., Wigderson, A. Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity 6, 3 (1997), 217--234.","journal-title":"Comput. Complexity"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535928"},{"key":"e_1_2_1_19_1","volume-title":"A survey of lower bounds in arithmetic circuit complexity. Github survey","author":"Saptharishi R.","year":"2015","unstructured":"Saptharishi, R. A survey of lower bounds in arithmetic circuit complexity. Github survey (2015)."},{"key":"e_1_2_1_20_1","first-page":"49","article-title":"Progress on polynomial identity testing","volume":"99","author":"Saxena N","year":"2009","unstructured":"Saxena, N. Progress on polynomial identity testing. Bull. EATCS 99 (2009), 49--79.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_23_1","volume-title":"Vermeidung von divisionen. J. f\u00fcr die reine und angewandte Mathematik 264","author":"Strassen V.","year":"1973","unstructured":"Strassen, V. Vermeidung von divisionen. J. f\u00fcr die reine und angewandte Mathematik 264 (1973), 184--202."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611094","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3611094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:50:53Z","timestamp":1750272653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,25]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.1145\/3611094"],"URL":"https:\/\/doi.org\/10.1145\/3611094","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,25]]},"assertion":[{"value":"2024-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}