{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:35Z","timestamp":1781077715519,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Russian Science Foundation","award":["Project 16-11-10123"],"award-info":[{"award-number":["Project 16-11-10123"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384245","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"page":"54-67","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Semi-algebraic proofs, IPS lower bounds, and the \u03c4-conjecture: can a natural number be negative?"],"prefix":"10.1145","author":[{"given":"Yaroslav","family":"Alekseev","sequence":"first","affiliation":[{"name":"Steklov Institute of Mathematics at St. Petersburg, Russia \/ St. Petersburg State University, Russia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dima","family":"Grigoriev","sequence":"additional","affiliation":[{"name":"CNRS, France \/ University of Lille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[{"name":"Steklov Institute of Mathematics at St. Petersburg, Russia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5558-9911","authenticated-orcid":false,"given":"Iddo","family":"Tzameret","sequence":"additional","affiliation":[{"name":"Royal Holloway University of London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"IPS Lower Bounds and the-Conjecture: Can a Natural Number be Negative? ArXiV: http:\/\/arxiv.org\/abs\/","author":"Alekseev Yaroslav","year":"1911","unstructured":"Yaroslav Alekseev , Dima Grigoriev , Edward A. Hirsch and Iddo Tzameret. SemiAlgebraic Proofs , IPS Lower Bounds and the-Conjecture: Can a Natural Number be Negative? ArXiV: http:\/\/arxiv.org\/abs\/ 1911 .06738 Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch and Iddo Tzameret. SemiAlgebraic Proofs, IPS Lower Bounds and the-Conjecture: Can a Natural Number be Negative? ArXiV: http:\/\/arxiv.org\/abs\/ 1911.06738"},{"key":"e_1_3_2_1_2_1","first-page":"24","volume-title":"34th Computational Complexity Conference, CCC 2019","author":"Atserias Albert","year":"2019","unstructured":"Albert Atserias and Tuomas Hakoniemi . Size-degree trade-ofs for sums-ofsquares and Positivstellensatz proofs . In 34th Computational Complexity Conference, CCC 2019 , pages 24 : 1-24 : 20, 2019 . Albert Atserias and Tuomas Hakoniemi. Size-degree trade-ofs for sums-ofsquares and Positivstellensatz proofs. In 34th Computational Complexity Conference, CCC 2019, pages 24 : 1-24 : 20, 2019."},{"key":"e_1_3_2_1_3_1","first-page":"307","volume-title":"STOC","author":"Barak Boaz","year":"2012","unstructured":"Boaz Barak , Fernando G. S. L. Brand\u00e3o , Aram Wettroth Harrow , Jonathan A. Kelner , David Steurer , and Yuan Zhou . Hypercontractivity, sum-of-squares proofs , and their applications . In STOC , pages 307 - 326 , 2012 . Boaz Barak, Fernando G. S. L. Brand\u00e3o, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In STOC, pages 307-326, 2012."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_3_2_1_5_1","first-page":"11","volume-title":"35th Symposium on Theoretical Aspects of Computer Science, STACS 2018","author":"Berkholz Christoph","year":"2018","unstructured":"Christoph Berkholz . The relation between polynomial calculus, sherali-adams, and sum-of-squares proofs . In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 , February 28 to March 3, 2018 , Caen, France, pages 11 : 1-11 : 14, 2018. Christoph Berkholz. The relation between polynomial calculus, sherali-adams, and sum-of-squares proofs. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 11 : 1-11 : 14, 2018."},{"key":"e_1_3_2_1_6_1","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry. MPS-SIAM Series on Optimization","author":"Blekherman Grigoriy","year":"2013","unstructured":"Grigoriy Blekherman , Pablo A. Parrilo , and Rekha Thomas , editors. Semidefinite Optimization and Convex Algebraic Geometry. MPS-SIAM Series on Optimization . Society for Industrial and Applied Mathematics (SIAM) , March 2013 . Grigoriy Blekherman, Pablo A. Parrilo, and Rekha Thomas, editors. Semidefinite Optimization and Convex Algebraic Geometry. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), March 2013."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_2_1_9_1","volume-title":"On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18 ( 1 ): 81-103","author":"B\u00fcrgisser Peter","year":"2009","unstructured":"Peter B\u00fcrgisser . On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18 ( 1 ): 81-103 , 2009 . Peter B\u00fcrgisser. On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18 ( 1 ): 81-103, 2009."},{"key":"e_1_3_2_1_10_1","volume-title":"Polynomial size proofs of the propositional pigeonhole principle. The Journal of Symbolic Logic, ( 52 ): 916-927","author":"Buss Samuel R.","year":"1987","unstructured":"Samuel R. Buss . Polynomial size proofs of the propositional pigeonhole principle. The Journal of Symbolic Logic, ( 52 ): 916-927 , 1987 . Samuel R. Buss. Polynomial size proofs of the propositional pigeonhole principle. The Journal of Symbolic Logic, ( 52 ): 916-927, 1987."},{"key":"e_1_3_2_1_11_1","volume-title":"Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity, 6 ( 3 ): 256-298","author":"Buss Samuel R.","year":"1996","unstructured":"Samuel R. Buss , Russell Impagliazzo , Jan Kraj\u00ed\u010dek , Pavel Pudl\u00e1k , Alexander A. Razborov , and Ji\u0159\u00ed Sgall . Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity, 6 ( 3 ): 256-298 , 1996 . Samuel R. Buss, Russell Impagliazzo, Jan Kraj\u00ed\u010dek, Pavel Pudl\u00e1k, Alexander A. Razborov, and Ji\u0159\u00ed Sgall. Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity, 6 ( 3 ): 256-298, 1996."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.020"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_14_1","first-page":"135","volume-title":"1974","author":"Stephen","year":"1974","unstructured":"Stephen A. Cook and Robert A. Reckhow. On the lengths of proofs in the propositional calculus (preliminary version) . In 1974 , pages 135 - 148 , 1974 . Stephen A. Cook and Robert A. Reckhow. On the lengths of proofs in the propositional calculus (preliminary version). In 1974, pages 135-148, 1974."},{"key":"e_1_3_2_1_15_1","volume-title":"The relative eficiency of propositional proof systems. J. Symb. Log., 44 ( 1 ): 36-50","author":"Cook Stephen A.","year":"1979","unstructured":"Stephen A. Cook and Robert A. Reckhow . The relative eficiency of propositional proof systems. J. Symb. Log., 44 ( 1 ): 36-50 , 1979 . Stephen A. Cook and Robert A. Reckhow. The relative eficiency of propositional proof systems. J. Symb. Log., 44 ( 1 ): 36-50, 1979."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-96-03173-5"},{"key":"e_1_3_2_1_17_1","volume-title":"Semialgebraic proofs and eficient algorithm design. Electronic Colloquium on Computational Complexity (ECCC), 26 : 106","author":"Fleming Noah","year":"2019","unstructured":"Noah Fleming , Pravesh Kothari , and Toniann Pitassi . Semialgebraic proofs and eficient algorithm design. Electronic Colloquium on Computational Complexity (ECCC), 26 : 106 , 2019 . Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and eficient algorithm design. Electronic Colloquium on Computational Complexity (ECCC), 26 : 106, 2019."},{"key":"e_1_3_2_1_18_1","first-page":"32","volume-title":"31st Conference on Computational Complexity, CCC 2016","author":"Forbes Michael A.","year":"2016","unstructured":"Michael A. Forbes , Amir Shpilka , Iddo Tzameret , and Avi Wigderson . Proof complexity lower bounds from algebraic circuit complexity . In 31st Conference on Computational Complexity, CCC 2016 , May 29 to June 1, 2016 , Tokyo, Japan, pages 32 : 1-32 : 17, 2016. Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. Proof complexity lower bounds from algebraic circuit complexity. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 32 : 1-32 : 17, 2016."},{"key":"e_1_3_2_1_19_1","volume-title":"4th Workshop, CSL ' 90, Heidelberg, Germany, October 1-5, 1990, Proceedings","volume":"533","author":"Goerdt Andreas","year":"1990","unstructured":"Andreas Goerdt . Cutting plane versus Frege proof systems. Computer Science Logic , 4th Workshop, CSL ' 90, Heidelberg, Germany, October 1-5, 1990, Proceedings , volume 533 of Lecture Notes in Computer Science, pages 174-194. Springer , 1990 . Andreas Goerdt. Cutting plane versus Frege proof systems. Computer Science Logic, 4th Workshop, CSL ' 90, Heidelberg, Germany, October 1-5, 1990, Proceedings, volume 533 of Lecture Notes in Computer Science, pages 174-194. Springer, 1990."},{"key":"e_1_3_2_1_20_1","volume-title":"10th Innovations in Theoretical Computer Science Conference, ITCS 2019","author":"G\u00f6\u00f6s Mika","year":"2019","unstructured":"Mika G\u00f6\u00f6s , Pritish Kamath , Robert Robere , and Dmitry Sokolov . Adventures in monotone complexity and TFNP . In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019 , January 10-12, 2019 , San Diego, California, USA, pages 38 : 1-38 : 19 , 2019. Mika G\u00f6\u00f6s, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 38 : 1-38 : 19, 2019."},{"key":"e_1_3_2_1_21_1","first-page":"1778","volume":"47","author":"G\u00f6\u00f6s Mika","year":"2018","unstructured":"Mika G\u00f6\u00f6s and Toniann Pitassi . Communication lower bounds via critical block sensitivity. SIAM J. Comput. , 47 ( 5 ): 1778 - 1806 , 2018 . Mika G\u00f6\u00f6s and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47 ( 5 ): 1778-1806, 2018.","journal-title":"J. Comput."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8192-0"},{"key":"e_1_3_2_1_23_1","volume-title":"Complexity of semialgebraic proofs. Mosc. Math. J., 2 ( 4 ): 647-679, 805","author":"Grigoriev Dima","year":"2002","unstructured":"Dima Grigoriev , Edward A. Hirsch , and Dmitrii V. Pasechnik . Complexity of semialgebraic proofs. Mosc. Math. J., 2 ( 4 ): 647-679, 805 , 2002 . Dima Grigoriev, Edward A. Hirsch, and Dmitrii V. Pasechnik. Complexity of semialgebraic proofs. Mosc. Math. J., 2 ( 4 ): 647-679, 805, 2002."},{"key":"e_1_3_2_1_24_1","first-page":"1","volume":"113","author":"Grigoriev Dima","year":"2002","unstructured":"Dima Grigoriev and Nicolai Vorobjov . Complexity of Null-and Positivstellensatz proofs. Ann. Pure Appl. Logic , 113 ( 1 - 3 ): 153-160, 2002 . Dima Grigoriev and Nicolai Vorobjov. Complexity of Null-and Positivstellensatz proofs. Ann. Pure Appl. Logic, 113 ( 1-3 ): 153-160, 2002.","journal-title":"Ann. Pure Appl. Logic"},{"key":"e_1_3_2_1_25_1","volume-title":"Grochow and Toniann Pitassi. Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. J. ACM, 65 ( 6 ): 37 : 1-37 : 59","author":"Joshua","year":"2018","unstructured":"Joshua A. Grochow and Toniann Pitassi. Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. J. ACM, 65 ( 6 ): 37 : 1-37 : 59 , 2018 . Joshua A. Grochow and Toniann Pitassi. Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. J. ACM, 65 ( 6 ): 37 : 1-37 : 59, 2018."},{"key":"e_1_3_2_1_26_1","volume-title":"Hilbert's invariant theory papers. Lie Groups: History, Frontiers and Applications","author":"Hilbert David","year":"1978","unstructured":"David Hilbert . Hilbert's invariant theory papers. Lie Groups: History, Frontiers and Applications , VIII. Math Sci Press, Brookline , Mass ., 1978 . Translated from the German by Michael Ackerman, With comments by Robert Hermann. David Hilbert. Hilbert's invariant theory papers. Lie Groups: History, Frontiers and Applications, VIII. Math Sci Press, Brookline, Mass., 1978. Translated from the German by Michael Ackerman, With comments by Robert Hermann."},{"key":"e_1_3_2_1_27_1","series-title":"Dagstuhl Seminar 18051","first-page":"124","volume-title":"Proof Complexity","author":"Hirsch Edward","year":"2018","unstructured":"Edward Hirsch and Iddo Tzameret . Nullstellensatz is equivalent to sum-ofsquares, over algebraic circuits . In Proof Complexity ( Dagstuhl Seminar 18051 ), pages 124 - 157 . Schloss Dagstuhl Leibniz-Zentrum fuer Informatik , 2018 ., Feb. 2018. https:\/\/materials.dagstuhl.de\/files\/18\/18051\/18051.IddoTzameret.Slides. pptx. Edward Hirsch and Iddo Tzameret. Nullstellensatz is equivalent to sum-ofsquares, over algebraic circuits. In Proof Complexity (Dagstuhl Seminar 18051), pages 124-157. Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, 2018., Feb. 2018. https:\/\/materials.dagstuhl.de\/files\/18\/18051\/18051.IddoTzameret.Slides. pptx."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214000"},{"key":"e_1_3_2_1_29_1","volume-title":"The surprising power of constant depth algebraic proofs. Electronic Colloquium on Computational Complexity (ECCC), 26 : 24","author":"Impagliazzo Russell","year":"2019","unstructured":"Russell Impagliazzo , Sasank Mouli , and Toniann Pitassi . The surprising power of constant depth algebraic proofs. Electronic Colloquium on Computational Complexity (ECCC), 26 : 24 , 2019 . Russell Impagliazzo, Sasank Mouli, and Toniann Pitassi. The surprising power of constant depth algebraic proofs. Electronic Colloquium on Computational Complexity (ECCC), 26 : 24, 2019."},{"key":"e_1_3_2_1_30_1","volume-title":"Lower bounds for the polynomial calculus and the gr\u00f6bner basis algorithm. Computational Complexity, 8 ( 2 ): 127-144","author":"Impagliazzo Russell","year":"1999","unstructured":"Russell Impagliazzo , Pavel Pudl\u00e1k , and Ji\u0159\u00ed Sgall . Lower bounds for the polynomial calculus and the gr\u00f6bner basis algorithm. Computational Complexity, 8 ( 2 ): 127-144 , 1999 . Russell Impagliazzo, Pavel Pudl\u00e1k, and Ji\u0159\u00ed Sgall. Lower bounds for the polynomial calculus and the gr\u00f6bner basis algorithm. Computational Complexity, 8 ( 2 ): 127-144, 1999."},{"key":"e_1_3_2_1_31_1","volume-title":"Lower bounds of static lovasz-schrijver calculus proofs for tseitin tautologies. Zapiski Nauchnyh Seminarov POMI, 340 : 10-32","author":"Itsykson Dmitry","year":"2006","unstructured":"Dmitry Itsykson and Arist Kojevnikov . Lower bounds of static lovasz-schrijver calculus proofs for tseitin tautologies. Zapiski Nauchnyh Seminarov POMI, 340 : 10-32 , 2006 . (in Russian). English translation appeared in Journal of Mathematical Sciences 145 ( 3 ): 4942-4952, 2007. Dmitry Itsykson and Arist Kojevnikov. Lower bounds of static lovasz-schrijver calculus proofs for tseitin tautologies. Zapiski Nauchnyh Seminarov POMI, 340 : 10-32, 2006. (in Russian). English translation appeared in Journal of Mathematical Sciences 145 ( 3 ): 4942-4952, 2007."},{"key":"e_1_3_2_1_32_1","volume-title":"Anneaux preordonnes. Journal d'Analyse Math\u00e9matique, 12 ( 1 ): 307-326","author":"Krivine J. L.","year":"1964","unstructured":"J. L. Krivine . Anneaux preordonnes. Journal d'Analyse Math\u00e9matique, 12 ( 1 ): 307-326 , 1964 . J. L. Krivine. Anneaux preordonnes. Journal d'Analyse Math\u00e9matique, 12 ( 1 ): 307-326, 1964."},{"key":"e_1_3_2_1_33_1","series-title":"SIAM Journal on Computing","first-page":"1424","volume-title":"Characterizing propositional proofs as noncommutative formulas","author":"Li Fu","year":"2018","unstructured":"Fu Li , Iddo Tzameret , and Zhengyu Wang . Characterizing propositional proofs as noncommutative formulas . In SIAM Journal on Computing , volume 47 , pages 1424 - 1462 , 2018 . Fu Li, Iddo Tzameret, and Zhengyu Wang. Characterizing propositional proofs as noncommutative formulas. In SIAM Journal on Computing, volume 47, pages 1424-1462, 2018."},{"key":"e_1_3_2_1_34_1","volume-title":"Stable sets and polynomials. Discrete Mathematics, 124 : 137-153","author":"Lov\u00e1sz L.","year":"1994","unstructured":"L. Lov\u00e1sz . Stable sets and polynomials. Discrete Mathematics, 124 : 137-153 , 1994 . L. Lov\u00e1sz. Stable sets and polynomials. Discrete Mathematics, 124 : 137-153, 1994."},{"key":"e_1_3_2_1_35_1","series-title":"SIAM Journal on Optimization, 1 : 166-190","volume-title":"Cones of matrices and set-functions and 0-1 optimization","author":"Lov\u00e1sz L.","year":"1991","unstructured":"L. Lov\u00e1sz and A. Schrijver . Cones of matrices and set-functions and 0-1 optimization . SIAM Journal on Optimization, 1 : 166-190 , 1991 . L. Lov\u00e1sz and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, 1 : 166-190, 1991."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.111"},{"key":"e_1_3_2_1_37_1","volume-title":"January, 2020","author":"Part Fedor","year":"2020","unstructured":"Fedor Part and Iddo Tzameret . Resolution with counting: Dag-like lower bounds and diferent moduli. To appear in 11th Innovations in Theoretical Computer Science Conference (ITCS) 2020 , January, 2020 , Seattle, WA, USA , 2020 . Fedor Part and Iddo Tzameret. Resolution with counting: Dag-like lower bounds and diferent moduli. To appear in 11th Innovations in Theoretical Computer Science Conference (ITCS) 2020, January, 2020, Seattle, WA, USA, 2020."},{"key":"e_1_3_2_1_38_1","series-title":"SIAM Journal on Computing, 37 ( 3 ): 845-869","volume-title":"Lower bounds for lov\u00e1szschrijver systems and beyond follow from multiparty communication complexity","author":"Paul Beame Toniann Pitassi","year":"2007","unstructured":"Toniann Pitassi Paul Beame and Nathan Segerlind . Lower bounds for lov\u00e1szschrijver systems and beyond follow from multiparty communication complexity . SIAM Journal on Computing, 37 ( 3 ): 845-869 , 2007 . Toniann Pitassi Paul Beame and Nathan Segerlind. Lower bounds for lov\u00e1szschrijver systems and beyond follow from multiparty communication complexity. SIAM Journal on Computing, 37 ( 3 ): 845-869, 2007."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Pitassi Toniann","year":"1998","unstructured":"Toniann Pitassi . Unsolvable systems of equations and proof complexity . In Proceedings of the International Congress of Mathematicians , Vol. III (Berlin, 1998 ), number Vol. III, pages 451-460, 1998. Toniann Pitassi. Unsolvable systems of equations and proof complexity. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998 ), number Vol. III, pages 451-460, 1998."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984450.2984455"},{"key":"e_1_3_2_1_41_1","series-title":"London Math","first-page":"197","volume-title":"Sets and proofs (Leeds","author":"Pudl\u00e1k Pavel","year":"1997","unstructured":"Pavel Pudl\u00e1k . On the complexity of the propositional calculus . In Sets and proofs (Leeds , 1997 ), volume 258 of London Math . Soc. Lecture Note Ser., pages 197 - 218 . Cambridge Univ. Press , Cambridge, 1999. Pavel Pudl\u00e1k. On the complexity of the propositional calculus. In Sets and proofs (Leeds, 1997 ), volume 258 of London Math. Soc. Lecture Note Ser., pages 197-218. Cambridge Univ. Press, Cambridge, 1999."},{"key":"e_1_3_2_1_42_1","volume-title":"Positive polynomials on compact semi-algebraic sets","author":"Putinar Mihai","year":"1993","unstructured":"Mihai Putinar . Positive polynomials on compact semi-algebraic sets . Indiana University Mathematics Journal , 42 ( 3 ): 969-984, 1993 . Mihai Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal, 42 ( 3 ): 969-984, 1993."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"e_1_3_2_1_45_1","first-page":"3","volume":"5","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka and Amir Yehudayof . Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science , 5 ( 3 - 4 ): 207-388, 2010 . Amir Shpilka and Amir Yehudayof. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5 ( 3-4): 207-388, 2010.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_2_1_46_1","volume-title":"\u201cNP\u2260P?\". Duke Math. J., 81 : 47-54","author":"Shub Michael","year":"1995","unstructured":"Michael Shub and Steve Smale . On the intractability of Hilbert's Nullstellensatz and an algebraic version of \u201cNP\u2260P?\". Duke Math. J., 81 : 47-54 , 1995 . Michael Shub and Steve Smale. On the intractability of Hilbert's Nullstellensatz and an algebraic version of \u201cNP\u2260P?\". Duke Math. J., 81 : 47-54, 1995."},{"key":"e_1_3_2_1_47_1","volume-title":"Mathematical problems for the next century. The Mathematical Intelligencer, 20 ( 2 ): 7-15","author":"Smale Steve","year":"1998","unstructured":"Steve Smale . Mathematical problems for the next century. The Mathematical Intelligencer, 20 ( 2 ): 7-15 , 1998 . Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer, 20 ( 2 ): 7-15, 1998."},{"key":"e_1_3_2_1_48_1","volume-title":"A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207 ( 2 ): 87-97","author":"Stengle Gilbert","year":"1974","unstructured":"Gilbert Stengle . A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207 ( 2 ): 87-97 , 1974 . Gilbert Stengle. A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207 ( 2 ): 87-97, 1974."},{"key":"e_1_3_2_1_49_1","first-page":"182","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen . Vermeidung von divisionen. J. Reine Angew. Math. , 264 : 182 - 202 , 1973 . (in German). Volker Strassen. Vermeidung von divisionen. J. Reine Angew. Math., 264 : 182-202, 1973. (in German).","journal-title":"Angew. Math."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_1_52_1","volume-title":"Logic and Algorithmic: International Symposium in honour of Ernst Specker, 30 : 365-380","author":"Valiant Leslie G.","year":"1982","unstructured":"Leslie G. Valiant . Reducibility by algebraic projections . Logic and Algorithmic: International Symposium in honour of Ernst Specker, 30 : 365-380 , 1982 . Leslie G. Valiant. Reducibility by algebraic projections. Logic and Algorithmic: International Symposium in honour of Ernst Specker, 30 : 365-380, 1982."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384245","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":51,"alternative-id":["10.1145\/3357713.3384245","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384245","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}