{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:48Z","timestamp":1750220088842,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T00:00:00Z","timestamp":1639958400000},"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":[[2021,12,20]]},"abstract":"<jats:p>Algebraic Natural Proofs is a recent framework which formalizes the type of reasoning used for proving most lower bounds on algebraic computational models. This concept is similar to and inspired by the famous natural proofs notion of Razborov and Rudich [RR97] for boolean circuit lower bounds, but, unlike in the boolean case, it is an open problem whether this constitutes a barrier for proving super-polynomial lower bounds for strong models of algebraic computation. From an algebraic-geometric viewpoint, it is also related to basic questions in Geometric Complexity Theory (GCT), and from a meta-complexity theoretic viewpoint, it can be seen as an algebraic version of the MCSP problem. We survey the recent work around this concept which provides some evidence both for and against the existence of an algebraic natural proofs barrier, with an emphasis on the di erent viewpoints and the connections to other areas.<\/jats:p>","DOI":"10.1145\/3510382.3510392","type":"journal-article","created":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T18:15:15Z","timestamp":1641233715000},"page":"56-73","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest Column"],"prefix":"10.1145","volume":"52","author":[{"given":"Ben Lee","family":"Volk","sequence":"first","affiliation":[{"name":"Reichman University, , Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_2_1","unstructured":"[AD08] Scott Aaronson and Andrew Drucker. Arithmetic natural proofs theory is sought. Blog post http:\/\/www.scottaaronson.com\/blog\/?p=336 2008.  [AD08] Scott Aaronson and Andrew Drucker. Arithmetic natural proofs theory is sought. Blog post http:\/\/www.scottaaronson.com\/blog\/?p=336 2008."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-40608-0_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_7_1","unstructured":"[BI17] Markus Blaser and Christian Ikenmeyer. Introduction to geometric complexity theory. Lecture notes http:\/\/pcwww.liv.ac.uk\/~iken\/teaching_sb\/summer17\/ introtogct\/gct.pdf 2017.  [BI17] Markus Blaser and Christian Ikenmeyer. Introduction to geometric complexity theory. Lecture notes http:\/\/pcwww.liv.ac.uk\/~iken\/teaching_sb\/summer17\/ introtogct\/gct.pdf 2017."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188832"},{"key":"e_1_2_1_9_1","volume-title":"Variety membership testing, algebraic natural proofs, and geometric complexity theory. CoRR, abs\/1911.02534","author":"Blaser Markus","year":"2019","unstructured":"[BIL+19] Markus Blaser , Christian Ikenmeyer , Vladimir Lysikov , Anurag Pandey , and Frank- Olaf Schreyer . Variety membership testing, algebraic natural proofs, and geometric complexity theory. CoRR, abs\/1911.02534 , 2019 . [BIL+19] Markus Blaser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank- Olaf Schreyer. Variety membership testing, algebraic natural proofs, and geometric complexity theory. CoRR, abs\/1911.02534, 2019."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.152"},{"key":"e_1_2_1_11_1","volume-title":"Fast Matrix Multiplication. Number 5 in Graduate Surveys","author":"Blaser Markus","year":"2013","unstructured":"[Bla13] Markus Blaser . Fast Matrix Multiplication. Number 5 in Graduate Surveys . Theory of Computing Library , 2013 . [Bla13] Markus Blaser. Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Computing Library, 2013."},{"issue":"1","key":"e_1_2_1_12_1","first-page":"88","article-title":"Theor","volume":"235","author":"Burgisser Peter","year":"2000","unstructured":"[Bur00] Peter Burgisser . Cook's versus Valiant's hypothesis. Theor . Comput. Sci. , 235 ( 1 ):71{ 88 , 2000 . [Bur00] Peter Burgisser. Cook's versus Valiant's hypothesis. Theor. Comput. Sci., 235(1):71{88, 2000.","journal-title":"Comput. Sci."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384283"},{"key":"e_1_2_1_14_1","first-page":"880","volume-title":"FOCS 2020","author":"Chatterjee Prerona","year":"2020","unstructured":"[CKR+20] Prerona Chatterjee , Mrinal Kumar , C. Ramya , Ramprasad Saptharishi , and Anamay Tengse . On the existence of algebraically natural proofs. In 61st IEEE Annual Sympo- sium on Foundations of Computer Science , FOCS 2020 , Durham, NC, USA, November 16--19 , 2020 , pages 870{ 880 . IEEE, 2020. [CKR+20] Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. On the existence of algebraically natural proofs. In 61st IEEE Annual Sympo- sium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16--19, 2020, pages 870{880. IEEE, 2020."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_17_1","first-page":"19","volume-title":"9th Innovations in Theoretical Computer Science Conference, ITCS 2018","volume":"94","author":"Efremenko Klim","year":"2018","unstructured":"[EGOW18] Klim Efremenko , Ankit Garg , Rafael Oliveira , and Avi Wigderson . Barriers for rank methods in arithmetic complexity . In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018 , January 11 --14 , 2018 , Cambridge, MA, USA, volume 94 of LIPIcs, pages 1:1{1: 19 . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2018. [EGOW18] Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11--14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 1:1{1:19. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2018."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.35"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a018"},{"key":"e_1_2_1_20_1","volume-title":"Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs\/1701.01717","author":"Grochow Joshua A.","year":"2017","unstructured":"[GKSS17] Joshua A. Grochow , Mrinal Kumar , Michael E. Saks , and Shubhangi Saraf . Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs\/1701.01717 , 2017 . [GKSS17] Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs\/1701.01717, 2017."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0141-z"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0103-x"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_2_1_24_1","volume-title":"Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 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. Comput. Complex., 13(1--2):1{46 , 2004 . [KI04] Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 13(1--2):1{46, 2004."},{"key":"e_1_2_1_25_1","volume-title":"If VNP is hard, then so are equations for it. CoRR, abs\/2012.07056","author":"Kumar Mrinal","year":"2020","unstructured":"[KRST20] Mrinal Kumar , C. Ramya , Ramprasad Saptharishi , and Anamay Tengse . If VNP is hard, then so are equations for it. CoRR, abs\/2012.07056 , 2020 . [KRST20] Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP is hard, then so are equations for it. CoRR, abs\/2012.07056, 2020."},{"key":"e_1_2_1_26_1","first-page":"129","article-title":"for algebraic computation","author":"Kumar Mrinal","year":"2019","unstructured":"[KS19] Mrinal Kumar and Ramprasad Saptharishi . Hardness-randomness tradeo s for algebraic computation . Bull. EATCS , 129 , 2019 . [KS19] Mrinal Kumar and Ramprasad Saptharishi. Hardness-randomness tradeo s for algebraic computation. Bull. EATCS, 129, 2019.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_27_1","first-page":"9","volume-title":"12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6--8, 2021, Virtual Conference","volume":"185","author":"Kumar Mrinal","unstructured":"[KV21] Mrinal Kumar and Ben Lee Volk . A polynomial degree bound on equations for nonrigid matrices and small linear circuits . In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6--8, 2021, Virtual Conference , volume 185 of LIPIcs, pages 9:1{9: 9 . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2021. [KV21] Mrinal Kumar and Ben Lee Volk. A polynomial degree bound on equations for nonrigid matrices and small linear circuits. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6--8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 9:1{9:9. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2021."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198338827"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00016"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_33_1","volume-title":"A survey of lower bounds in arithmetic circuit complexity. Github survey, https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/","author":"Saptharishi Ramprasad","year":"2016","unstructured":"[Sap16] Ramprasad Saptharishi . A survey of lower bounds in arithmetic circuit complexity. Github survey, https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/ , 2016 . [Sap16] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/, 2016."},{"key":"e_1_2_1_34_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 . Bull. EATCS , 99 : 49 {79, 2009 . [Sax09] Nitin Saxena. Progress on polynomial identity testing. Bull. EATCS, 99:49{79, 2009.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_35_1","series-title":"Progr","first-page":"146","volume-title":"Perspectives in com- putational complexity","author":"Saxena Nitin","unstructured":"[Sax14] Nitin Saxena . Progress on polynomial identity testing-II . In Perspectives in com- putational complexity , volume 26 of Progr . Comput. Sci. Appl. Logic , pages 131{ 146 . Birkhauser\/Springer, Cham, 2014. [Sax14] Nitin Saxena. Progress on polynomial identity testing-II. In Perspectives in com- putational complexity, volume 26 of Progr. Comput. Sci. Appl. Logic, pages 131{146. Birkhauser\/Springer, Cham, 2014."},{"issue":"3","key":"e_1_2_1_36_1","first-page":"356","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen Volker","year":"1969","unstructured":"[Str69] Volker Strassen . Gaussian elimination is not optimal . Numerische Mathematik , 13 ( 3 ):354{ 356 , 1969 . [Str69] Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13(3):354{356, 1969.","journal-title":"Numerische Mathematik"},{"key":"e_1_2_1_37_1","volume-title":"Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3--4):207{388","author":"Shpilka Amir","year":"2010","unstructured":"[SY10] Amir Shpilka and Amir Yehudayo . Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3--4):207{388 , 2010 . [SY10] Amir Shpilka and Amir Yehudayo . Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3--4):207{388, 2010."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510382.3510392","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3510382.3510392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:45Z","timestamp":1750183785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510382.3510392"}},"subtitle":["Algebraic Natural Proofs Ben Lee Volk"],"short-title":[],"issued":{"date-parts":[[2021,12,20]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,20]]}},"alternative-id":["10.1145\/3510382.3510392"],"URL":"https:\/\/doi.org\/10.1145\/3510382.3510392","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2021,12,20]]},"assertion":[{"value":"2022-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}