{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:45Z","timestamp":1750220145731,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2022,6,10]]},"abstract":"<jats:p>Given a polynomial fpx1; : : : ; xNq, we can wonder how we can evaluate it with a minimal number of arithmetic operations. Indeed, the task of the algorithm designer is to nd evolved processes which decrease this number. In the other direction, it could be interesting to be able to prove that there is no algorithm which does the computation in less than some number of operations. But how one could prove something like that? We will present here some methods which allow us to tackle the problem in the case of constant-depth algebraic circuits.<\/jats:p>","DOI":"10.1145\/3544979.3544989","type":"journal-article","created":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T16:16:25Z","timestamp":1658765785000},"page":"40-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest Column"],"prefix":"10.1145","volume":"53","author":[{"given":"N.","family":"Limaye","sequence":"first","affiliation":[{"name":"ITU Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Tavenas","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, Univ. Savoie Mont Blanc, CNRS, LAMA, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792540"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_5_1","first-page":"522","volume-title":"Proceedings of Symposium on Discrete Algorithms","author":"Alman Josh","year":"2021","unstructured":"[AW21] Josh Alman and Virginia Vassilevska Williams . A re ned laser method and faster matrix multiplication . In Proceedings of Symposium on Discrete Algorithms , pages 522 - 539 . SIAM, 2021 . [AW21] Josh Alman and Virginia Vassilevska Williams. A re ned laser method and faster matrix multiplication. In Proceedings of Symposium on Discrete Algorithms, pages 522-539. SIAM, 2021."},{"key":"e_1_2_1_6_1","first-page":"183","volume-title":"Proceedings of Conference on Computational Complexity","volume":"33","author":"Suman","year":"2015","unstructured":"[BC15] Suman K. Bera and Amit Chakrabarti. A depth- ve lower bound for Iterated Matrix Multiplication . In Proceedings of Conference on Computational Complexity , volume 33 of LIPIcs, pages 183 - 197 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 2015 . [BC15] Suman K. Bera and Amit Chakrabarti. A depth- ve lower bound for Iterated Matrix Multiplication. In Proceedings of Conference on Computational Complexity, volume 33 of LIPIcs, pages 183-197. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2015."},{"key":"e_1_2_1_7_1","first-page":"934","volume-title":"Proceedings of Foundations of Computer Science","author":"Chillara Suryajith","year":"2018","unstructured":"[CELS18] Suryajith Chillara , Christian Engels , Nutan Limaye , and Srikanth Srinivasan . A nearoptimal depth-hierarchy theorem for small-depth multilinear circuits . In Proceedings of Foundations of Computer Science , pages 934 - 945 , 2018 . [CELS18] Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. A nearoptimal depth-hierarchy theorem for small-depth multilinear circuits. In Proceedings of Foundations of Computer Science, pages 934-945, 2018."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a013"},{"key":"e_1_2_1_9_1","volume-title":"The chasm at depth four, and tensor rank: Old results, new insights. CoRR, abs\/1606.04200","author":"Chillara Suryajith","year":"2016","unstructured":"[CKSV16] Suryajith Chillara , Mrinal Kumar , Ramprasad Saptharishi , and V. Vinay . The chasm at depth four, and tensor rank: Old results, new insights. CoRR, abs\/1606.04200 , 2016 . [CKSV16] Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, and V. Vinay. The chasm at depth four, and tensor rank: Old results, new insights. CoRR, abs\/1606.04200, 2016."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1191567"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of Conference on Computational Complexity, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021","volume":"53","author":"Dutta Pranjal","year":"2022","unstructured":"[DDS21] Pranjal Dutta , Prateek Dwivedi , and Nitin Saxena . Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits . In Proceedings of Conference on Computational Complexity, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021 . ACM SIGACT News 58 June 2022 , vol. 53 , no. 2 [DDS21] Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. In Proceedings of Conference on Computational Complexity, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021. ACM SIGACT News 58 June 2022, vol. 53, no. 2"},{"key":"e_1_2_1_12_1","volume-title":"Georgia Inst. of Tech Atlanta School of Information and Computer Science","author":"DeMillo Richard A","year":"1977","unstructured":"[DL77] Richard A DeMillo and Richard J Lipton . A probabilistic remark on algebraic program testing. Technical report , Georgia Inst. of Tech Atlanta School of Information and Computer Science , 1977 . [DL77] Richard A DeMillo and Richard J Lipton. A probabilistic remark on algebraic program testing. Technical report, Georgia Inst. of Tech Atlanta School of Information and Computer Science, 1977."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214034"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188760"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1957999"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1097870"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990280"},{"key":"e_1_2_1_19_1","volume-title":"circuits, and the polynomialtime hierarchy. Mathematical systems theory, 17(1):13-27","author":"Furst Merrick","year":"1984","unstructured":"[FSS84] Merrick Furst , James B. Saxe , and Michael Sipser . Parity , circuits, and the polynomialtime hierarchy. Mathematical systems theory, 17(1):13-27 , 1984 . [FSS84] Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomialtime hierarchy. Mathematical systems theory, 17(1):13-27, 1984."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.95"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957123"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00018"},{"key":"e_1_2_1_25_1","first-page":"6","volume-title":"Proceedings of Symposium on Theory of Computing","volume":"53","author":"H","year":"1986","unstructured":"[ H 86] Johan H astad. Almost optimal lower bounds for small depth circuits . In Proceedings of Symposium on Theory of Computing , page 6 - 20 , 1986 . ACM SIGACT News 59 June 2022, vol. 53 , no. 2 [H 86] Johan H astad. Almost optimal lower bounds for small depth circuits. In Proceedings of Symposium on Theory of Computing, page 6-20, 1986. ACM SIGACT News 59 June 2022, vol. 53, no. 2"},{"key":"e_1_2_1_26_1","first-page":"171","volume-title":"Proceedings of Symposium on Foundations of Computer Science","author":"Laurent Hya","year":"1977","unstructured":"[Hya77] Laurent Hya l. The power of commutativity . In Proceedings of Symposium on Foundations of Computer Science , pages 171 - 174 , 1977 . [Hya77] Laurent Hya l. The power of commutativity. In Proceedings of Symposium on Foundations of Computer Science, pages 171-174, 1977."},{"key":"e_1_2_1_27_1","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":"[Kay12] Neeraj Kayal . An exponential lower bound for the sum of powers of bounded degree polynomials . Electronic Colloquium on Computional Complexity , 19 : 81 , 2012 . [Kay12] Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computional Complexity, 19:81, 2012.","journal-title":"Electronic Colloquium on Computional Complexity"},{"key":"e_1_2_1_28_1","volume-title":"Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1--2):1-46","author":"Kabanets Valentine","year":"2004","unstructured":"[KI04] Valentine Kabanets and Russell Impagliazzo . Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1--2):1-46 , 2004 . [KI04] Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1--2):1-46, 2004."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002423"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/110824516"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2537-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0132-0"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/140999335"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197406.3197416"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1173319"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.25"},{"key":"e_1_2_1_39_1","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"1","volume-title":"Proceedings of International Colloquium on Automata, Languages, and Programming","author":"Kayal Neeraj","year":"2016","unstructured":"[KST16] Neeraj Kayal , Chandan Saha , and S ebastien Tavenas . An almost cubic lower bound for depth three arithmetic circuits . In Proceedings of International Colloquium on Automata, Languages, and Programming , volume 55 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 33: 1 - 33 :15, 2016 . [KST16] Neeraj Kayal, Chandan Saha, and S ebastien Tavenas. An almost cubic lower bound for depth three arithmetic circuits. In Proceedings of International Colloquium on Automata, Languages, and Programming, volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:15, 2016."},{"key":"e_1_2_1_40_1","first-page":"565","volume-title":"Proceedings of Fundamentals of Computation Theory","volume":"79","author":"L","year":"1979","unstructured":"[Lov79] L aszl o Lov asz. On determinants, matchings, and random algorithms . In Proceedings of Fundamentals of Computation Theory , volume 79 , pages 565 - 574 , 1979 . ACM SIGACT News 60 June 2022, vol. 53, no. 2 [Lov79] L aszl o Lov asz. On determinants, matchings, and random algorithms. In Proceedings of Fundamentals of Computation Theory, volume 79, pages 565-574, 1979. ACM SIGACT News 60 June 2022, vol. 53, no. 2"},{"key":"e_1_2_1_41_1","first-page":"94","volume-title":"Set-multilinear and noncommutative formula lower bounds for iterated matrix multiplication. To appear in Proceedings of Symposium on Theory of Computing","author":"Limaye Nutan","year":"2022","unstructured":"[LST21a] Nutan Limaye , Srikanth Srinivasan , and S ebastien Tavenas . Set-multilinear and noncommutative formula lower bounds for iterated matrix multiplication. To appear in Proceedings of Symposium on Theory of Computing , 2022 . Electronic Colloquium on Computational Complexity , page 94 , 2021. [LST21a] Nutan Limaye, Srikanth Srinivasan, and S ebastien Tavenas. Set-multilinear and noncommutative formula lower bounds for iterated matrix multiplication. To appear in Proceedings of Symposium on Theory of Computing, 2022. Electronic Colloquium on Computational Complexity, page 94, 2021."},{"key":"e_1_2_1_42_1","first-page":"804","volume-title":"Proceedings of Symposium on Foundations of Computer Science","author":"Limaye Nutan","year":"2021","unstructured":"[LST21b] Nutan Limaye , Srikanth Srinivasan , and S ebastien Tavenas . Superpolynomial lower bounds against low-depth algebraic circuits . In Proceedings of Symposium on Foundations of Computer Science , pages 804 - 814 , 2021 . [LST21b] Nutan Limaye, Srikanth Srinivasan, and S ebastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In Proceedings of Symposium on Foundations of Computer Science, pages 804-814, 2021."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_46_1","first-page":"1","volume-title":"Proceedings of Computational Complexity Conference","volume":"169","author":"Peleg Shir","year":"2020","unstructured":"[PS20] Shir Peleg and Amir Shpilka . A generalized sylvester-gallai type theorem for quadratic polynomials . In Proceedings of Computational Complexity Conference , volume 169 of LIPIcs, pages 8: 1 - 8 :33. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 2020 . [PS20] Shir Peleg and Amir Shpilka. A generalized sylvester-gallai type theorem for quadratic polynomials. In Proceedings of Computational Complexity Conference, volume 169 of LIPIcs, pages 8:1-8:33. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"e_1_2_1_47_1","first-page":"259","volume-title":"Proceedings of Symposium on Theory of Computing","author":"Peleg Shir","year":"2021","unstructured":"[PS21] Shir Peleg and Amir Shpilka . Polynomial time deterministic identity testing algorithm for r3s r2s circuits via Edelstein-Kelly type theorem for quadratic polynomials . In Proceedings of Symposium on Theory of Computing , pages 259 - 271 , 2021 . [PS21] Shir Peleg and Amir Shpilka. Polynomial time deterministic identity testing algorithm for r3s r2s circuits via Edelstein-Kelly type theorem for quadratic polynomials. In Proceedings of Symposium on Theory of Computing, pages 259-271, 2021."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a006"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535928"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_2_1_54_1","volume-title":"A survey of lower bounds in arithmetic circuit complexity. Github survey","author":"Saptharishi Ramprasad","year":"2015","unstructured":"[Sap15] Ramprasad Saptharishi . A survey of lower bounds in arithmetic circuit complexity. Github survey , 2015 . [Sap15] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015."},{"key":"e_1_2_1_55_1","first-page":"49","article-title":"Progress on polynomial identity testing","volume":"99","author":"Saxena Nitin","year":"2009","unstructured":"[Sax09] Nitin Saxena . Progress on polynomial identity testing . Bulletin of EATCS , 99 : 49 - 79 , 2009 . ACM SIGACT News 61 June 2022, vol. 53, no. 2 [Sax09] Nitin Saxena. Progress on polynomial identity testing. Bulletin of EATCS, 99:49-79, 2009. ACM SIGACT News 61 June 2022, vol. 53, no. 2","journal-title":"Bulletin of EATCS"},{"key":"e_1_2_1_56_1","volume-title":"Progress on polynomial identity testing - II. Electronic Colloquium on Computational Complexity, page 186","author":"Saxena Nitin","year":"2013","unstructured":"[Sax13] Nitin Saxena . Progress on polynomial identity testing - II. Electronic Colloquium on Computational Complexity, page 186 , 2013 . [Sax13] Nitin Saxena. Progress on polynomial identity testing - II. Electronic Colloquium on Computational Complexity, page 186, 2013."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/10848232"},{"key":"e_1_2_1_59_1","first-page":"184","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"[Str73] Volker Strassen . Vermeidung von divisionen . Journal fur die reine und angewandte Mathematik , 264 : 184 - 202 , 1973 . [Str73] Volker Strassen. Vermeidung von divisionen. Journal fur die reine und angewandte Mathematik, 264:184-202, 1973.","journal-title":"Journal fur die reine und angewandte Mathematik"},{"key":"e_1_2_1_60_1","first-page":"553","volume-title":"Doklady Akademii Nauk","author":"Subbotovskaya Bella A.","year":"1961","unstructured":"[Sub61] Bella A. Subbotovskaya . Realization of linear functions by formulas using ^, _ , . In Doklady Akademii Nauk , volume 136- 3 , pages 553 - 555 . Russian Academy of Sciences , 1961 . [Sub61] Bella A. Subbotovskaya. Realization of linear functions by formulas using ^, _, . In Doklady Akademii Nauk, volume 136-3, pages 553-555. Russian Academy of Sciences, 1961."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3460-4"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_2_1_63_1","volume-title":"Arithmetic circuits: A survey of recent results and open questions","author":"Shpilka Amir","year":"2010","unstructured":"[SY10] Amir Shpilka and Amir Yehudayo . Arithmetic circuits: A survey of recent results and open questions . Now Publishers Inc , 2010 . [SY10] Amir Shpilka and Amir Yehudayo . Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544979.3544989","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3544979.3544989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:01Z","timestamp":1750186801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544979.3544989"}},"subtitle":["Lower Bounds Against Constant-Depth Algebraic Circuits"],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,10]]}},"alternative-id":["10.1145\/3544979.3544989"],"URL":"https:\/\/doi.org\/10.1145\/3544979.3544989","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}