{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T11:17:02Z","timestamp":1648898222308},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2021,12,20]]},"abstract":"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","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"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"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"},{"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"},{"issue":"1","key":"e_1_2_1_12_1","first-page":"88","article-title":"Theor","volume":"235","author":"Burgisser Peter","year":"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"},{"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"},{"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"},{"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"},{"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"},{"key":"e_1_2_1_26_1","first-page":"129","article-title":"for algebraic computation","author":"Kumar Mrinal","year":"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"},{"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"},{"key":"e_1_2_1_34_1","first-page":"49","article-title":"Progress on polynomial identity testing","volume":"99","author":"Saxena Nitin","year":"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"},{"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","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"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3510382.3510392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T05:25:00Z","timestamp":1643693100000},"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":"http:\/\/dx.doi.org\/10.1145\/3510382.3510392","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"published":{"date-parts":[[2021,12,20]]}}}