{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:46:11Z","timestamp":1773996371907,"version":"3.50.1"},"reference-count":108,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,11,26]],"date-time":"2018-11-26T00:00:00Z","timestamp":1543190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["# 482671"],"award-info":[{"award-number":["# 482671"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DMS-1620484"],"award-info":[{"award-number":["DMS-1620484"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Santa Fe Institute Omidyar Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>\n            We introduce a new and natural algebraic proof system, whose complexity measure is essentially the algebraic circuit size of Nullstellensatz certificates. This enables us to exhibit close connections between effective Nullstellensatz\u00eb, proof complexity, and (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits (VNP \u2260 VP). We also show that super-polynomial lower bounds on the number of lines in Polynomial Calculus proofs imply the Permanent versus Determinant Conjecture. Note that there was no proof system prior to ours for which lower bounds on an arbitrary tautology implied\n            <jats:italic>any<\/jats:italic>\n            complexity class lower bound.\n          <\/jats:p>\n          <jats:p>\n            Our proof system helps clarify the relationships between previous algebraic proof systems. In doing so, we highlight the importance of polynomial identity testing (PIT) in proof complexity. In particular, we use PIT to illuminate AC\n            <jats:sup>0<\/jats:sup>\n            [\n            <jats:italic>p<\/jats:italic>\n            ]-Frege lower bounds, which have been open for nearly 30 years, with no satisfactory explanation as to their apparent difficulty.\n          <\/jats:p>\n          <jats:p>\n            Finally, we explain the obstacles that must be overcome in any attempt to extend techniques from algebraic circuit complexity to prove lower bounds in proof complexity. Using the algebraic structure of our proof system, we propose a novel route to such lower bounds. Although such lower bounds remain elusive, this proposal should be contrasted with the difficulty of extending AC\n            <jats:sup>0<\/jats:sup>\n            [\n            <jats:italic>p<\/jats:italic>\n            ] circuit lower bounds to AC\n            <jats:sup>0<\/jats:sup>\n            [\n            <jats:italic>p<\/jats:italic>\n            ]-Frege lower bounds.\n          <\/jats:p>","DOI":"10.1145\/3230742","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T13:18:59Z","timestamp":1543324739000},"page":"1-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Circuit Complexity, Proof Complexity, and Polynomial Identity Testing"],"prefix":"10.1145","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6466-0476","authenticated-orcid":false,"given":"Joshua A.","family":"Grochow","sequence":"first","affiliation":[{"name":"University of Colorado at Boulder and Santa Fe Institute"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"University of Toronto and Institute for Advanced Study"}]}],"member":"320","published-online":{"date-parts":[[2018,11,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302964"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366735"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_6_1","unstructured":"M. F. Atiyah and I. G. Macdonald. 1969. Introduction to Commutative Algebra. Addison-Wesley Publishing Co. Reading MA.  M. F. Atiyah and I. G. Macdonald. 1969. Introduction to Commutative Algebra. Addison-Wesley Publishing Co. Reading MA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_10_1","volume-title":"What can be computed in algebraic geometry? In Computational Algebraic Geometry and Commutative Algebra (Cortona","author":"Bayer Dave","year":"1991","unstructured":"Dave Bayer and David Mumford . 1993. What can be computed in algebraic geometry? In Computational Algebraic Geometry and Commutative Algebra (Cortona , 1991 ). Cambridge University Press , Cambridge , 1--48. Dave Bayer and David Mumford. 1993. What can be computed in algebraic geometry? In Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991). Cambridge University Press, Cambridge, 1--48."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389151"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-87-05517-7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80039-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129733"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62241"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275569"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0183-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798353230"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971361"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1030132301"},{"key":"e_1_2_1_22_1","volume-title":"Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics","author":"B\u00fcrgisser Peter","unstructured":"Peter B\u00fcrgisser . 2000. Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics , Vol. 7 . Springer-Verlag , Berlin . Peter B\u00fcrgisser. 2000. Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics, Vol. 7. Springer-Verlag, Berlin."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00183-8"},{"key":"e_1_2_1_24_1","volume-title":"Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}","author":"B\u00fcrgisser Peter","unstructured":"Peter B\u00fcrgisser , Michael Clausen , and M. Amin Shokrollahi . 1997. Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences} , Vol. 315 . Springer-Verlag , Berlin . Peter B\u00fcrgisser, Michael Clausen, and M. Amin Shokrollahi. 1997. Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}, Vol. 315. Springer-Verlag, Berlin."},{"key":"e_1_2_1_25_1","volume-title":"Leibniz International Proceedings in Informatics (LIPIcs)","volume":"40","author":"Carmosino Marco L.","year":"2015","unstructured":"Marco L. Carmosino , Russell Impagliazzo , Valentine Kabanets , and Antonina Kolokolova . 2015 . Tighter connections between derandomization and circuit lower bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915) , Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 40 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 645--658. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. 2015. Tighter connections between derandomization and circuit lower bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 40. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 645--658."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000043"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002220050332"},{"key":"e_1_2_1_31_1","volume-title":"Graduate Texts in Mathematics","author":"Eisenbud David","unstructured":"David Eisenbud . 1995. Commutative Algebra . Graduate Texts in Mathematics , Vol. 150 . Springer-Verlag , New York . NY. David Eisenbud. 1995. Commutative Algebra. Graduate Texts in Mathematics, Vol. 150. Springer-Verlag, New York. NY."},{"key":"e_1_2_1_32_1","volume-title":"Gr\u00f6bner Bases in Commutative Algebra. Graduate Studies in Mathematics","author":"Ene Viviana","unstructured":"Viviana Ene and J\u00fcrgen Herzog . 2012. Gr\u00f6bner Bases in Commutative Algebra. Graduate Studies in Mathematics , Vol. 130 . American Mathematical Society , Providence, RI . Viviana Ene and J\u00fcrgen Herzog. 2012. Gr\u00f6bner Bases in Commutative Algebra. Graduate Studies in Mathematics, Vol. 130. American Mathematical Society, Providence, RI."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u201916), Ran Raz (Ed.), Leibniz International Proceedings in Informatics (LIPIcs)","volume":"50","author":"Forbes Michael A.","year":"2016","unstructured":"Michael A. Forbes , Amir Shpilka , Iddo Tzameret , and Avi Wigderson . 2016 . Proof complexity lower bounds from algebraic circuit complexity . In Proceedings of the 31st Conference on Computational Complexity (CCC\u201916), Ran Raz (Ed.), Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 50 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 32:1--32:17. Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. 2016. Proof complexity lower bounds from algebraic circuit complexity. In Proceedings of the 31st Conference on Computational Complexity (CCC\u201916), Ran Raz (Ed.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 50. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 32:1--32:17."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00446-2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0103-x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.20"},{"key":"e_1_2_1_38_1","volume-title":"Grochow and Toniann Pitassi","author":"Joshua","year":"2017","unstructured":"Joshua A. Grochow and Toniann Pitassi . 2017 . Tighter depth-preserving simulation of AC<sup>0<\/sup>{p}-Frege by the Ideal Proof System . (unpublished). Joshua A. Grochow and Toniann Pitassi. 2017. Tighter depth-preserving simulation of AC<sup>0<\/sup>{p}-Frege by the Ideal Proof System. (unpublished)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.68"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"e_1_2_1_42_1","volume-title":"Logic and Algorithmic (Zurich","author":"Heintz Joos","year":"1980","unstructured":"Joos Heintz and C.-P. Schnorr . 1982. Testing polynomials which are easy to compute . In Logic and Algorithmic (Zurich , 1980 ). Monograph. Enseign. Math., Vol. 30 . Univ. Gen\u00e8ve , Geneva, 237--254. Joos Heintz and C.-P. Schnorr. 1982. Testing polynomials which are easy to compute. In Logic and Algorithmic (Zurich, 1980). Monograph. Enseign. Math., Vol. 30. Univ. Gen\u00e8ve, Geneva, 237--254."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206635"},{"key":"e_1_2_1_44_1","volume-title":"Hilbert\u2019s Invariant Theory Papers","author":"Hilbert David","unstructured":"David Hilbert . 1978. Hilbert\u2019s Invariant Theory Papers . Math Sci Press , Brookline, MA . David Hilbert. 1978. Hilbert\u2019s Invariant Theory Papers. Math Sci Press, Brookline, MA."},{"key":"e_1_2_1_45_1","volume-title":"Tel Aviv","author":"Hrube\u0161 Pavel","year":"2016","unstructured":"Pavel Hrube\u0161 . 2016 . Arithmetic circuits and proof complexity. (2016). Talks given at the Workshop on Algebraic Complexity Theory , Tel Aviv , Israel , 2016. Pavel Hrube\u0161. 2016. Arithmetic circuits and proof complexity. (2016). Talks given at the Workshop on Algebraic Complexity Theory, Tel Aviv, Israel, 2016."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.9"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213998"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201912). Leibniz Int. Proc. Inform. (LIPIcs)","volume":"14","author":"Jansen Maurice","year":"2012","unstructured":"Maurice Jansen and Rahul Santhanam . 2012 . Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes . In Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201912). Leibniz Int. Proc. Inform. (LIPIcs) , Vol. 14 . Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 519--530. Maurice Jansen and Rahul Santhanam. 2012. Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes. In Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201912). Leibniz Int. Proc. Inform. (LIPIcs), Vol. 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 519--530."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0434-8"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/646361.690740"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.15"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0019"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.2307\/1990996"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100970050009"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275250"},{"key":"e_1_2_1_59_1","volume-title":"Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and Its Applications","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek . 1995. Bounded Arithmetic , Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and Its Applications , Vol. 60 . Cambridge University Press , Cambridge . Jan Kraj\u00ed\u010dek. 1995. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and Its Applications, Vol. 60. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-01-10934-4"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 32nd IEEE Conference on Computational Complexity (CCC\u201917)","author":"Kumar Mrinal","year":"2015","unstructured":"Mrinal Kumar and Ramprasad Saptharishi . 2015 . An exponential lower bound for homogeneous depth-5 circuits over finite fields . In Proceedings of the 32nd IEEE Conference on Computational Complexity (CCC\u201917) . 31:1--31:30. Preprint available as ECCC Tech. Report TR15-109. Mrinal Kumar and Ramprasad Saptharishi. 2015. An exponential lower bound for homogeneous depth-5 circuits over finite fields. In Proceedings of the 32nd IEEE Conference on Computational Complexity (CCC\u201917). 31:1--31:30. Preprint available as ECCC Tech. Report TR15-109."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.46"},{"key":"e_1_2_1_64_1","volume-title":"Geometric complexity theory: An introduction for geometers. Annali Dell\u2019universit\u00e1 di Ferrara 61, 1","author":"Landsberg J. M.","year":"2014","unstructured":"J. M. Landsberg . 2014. Geometric complexity theory: An introduction for geometers. Annali Dell\u2019universit\u00e1 di Ferrara 61, 1 ( 2014 ), 1--53. J. M. Landsberg. 2014. Geometric complexity theory: An introduction for geometers. Annali Dell\u2019universit\u00e1 di Ferrara 61, 1 (2014), 1--53."},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 30th Conference on Computational Complexity (CCC\u201915), David Zuckerman (Ed.), Leibniz International Proceedings in Informatics (LIPIcs)","volume":"33","author":"Li Fu","year":"2015","unstructured":"Fu Li , Iddo Tzameret , and Zhengyu Wang . 2015 . Non-commutative formulas and Frege lower bounds: A new characterization of propositional proofs . In Proceedings of the 30th Conference on Computational Complexity (CCC\u201915), David Zuckerman (Ed.), Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 33 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 412--432. Fu Li, Iddo Tzameret, and Zhengyu Wang. 2015. Non-commutative formulas and Frege lower bounds: A new characterization of propositional proofs. In Proceedings of the 30th Conference on Computational Complexity (CCC\u201915), David Zuckerman (Ed.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 33. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 412--432."},{"key":"e_1_2_1_66_1","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Compute Science","volume":"39","author":"Maciel Alexis","year":"1998","unstructured":"Alexis Maciel and Toniann Pitassi . 1998 . Towards lower bounds for bounded-depth Frege proofs with modular connectives. In Proof Complexity and Feasible Arithmetics, Paul Beame and Sam Buss (Eds.) . DIMACS Series in Discrete Mathematics and Theoretical Compute Science , Vol. 39 . American Mathematical Society, 195--227. Alexis Maciel and Toniann Pitassi. 1998. Towards lower bounds for bounded-depth Frege proofs with modular connectives. In Proof Complexity and Feasible Arithmetics, Paul Beame and Sam Buss (Eds.). DIMACS Series in Discrete Mathematics and Theoretical Compute Science, Vol. 39. American Mathematical Society, 195--227."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.09.006"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01398396"},{"key":"e_1_2_1_69_1","volume-title":"Commutative Algebra","author":"Matsumura Hideyuki","unstructured":"Hideyuki Matsumura . 1980. Commutative Algebra ( 2 nd ed.). Mathematics Lecture Note Series, Vol . 56. Benjamin\/Cummings Publishing Co. , Inc., Reading, MA. Hideyuki Matsumura. 1980. Commutative Algebra (2nd ed.). Mathematics Lecture Note Series, Vol. 56. Benjamin\/Cummings Publishing Co., Inc., Reading, MA.","edition":"2"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/73228.73262"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833251"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698831"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794282930"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184341"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718115"},{"key":"e_1_2_1_79_1","volume-title":"Complex Projective Varieties. Number 221 in Grundlehren der Mathematischen Wissenschaften","author":"Mumford David","unstructured":"David Mumford . 1976. Algebraic Geometry I. Complex Projective Varieties. Number 221 in Grundlehren der Mathematischen Wissenschaften . Springer-Verlag , Berlin . David Mumford. 1976. Algebraic Geometry I. Complex Projective Varieties. Number 221 in Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_81_1","volume-title":"Proceedings of the Descriptive Complexity and Finite Models Workshop (DIMACS\u201996)","volume":"31","author":"Pitassi Toniann","year":"1996","unstructured":"Toniann Pitassi . 1996 . Algebraic propositional proof systems . In Proceedings of the Descriptive Complexity and Finite Models Workshop (DIMACS\u201996) . Neil Immerman and Phokion G. Kolaitis (Eds.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Vol. 31 . American Mathematical Society, 215--244. Toniann Pitassi. 1996. Algebraic propositional proof systems. In Proceedings of the Descriptive Complexity and Finite Models Workshop (DIMACS\u201996). Neil Immerman and Phokion G. Kolaitis (Eds.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 31. American Mathematical Society, 215--244."},{"key":"e_1_2_1_82_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Pitassi Toniann","year":"1998","unstructured":"Toniann Pitassi . 1998 . Unsolvable systems of equations and proof complexity . In Proceedings of the International Congress of Mathematicians , Vol. III , Berlin, 451--460. https:\/\/www.emis.de\/journals\/DMJDMV\/xvolicm\/14\/Pitassi.MAN.html. Toniann Pitassi. 1998. Unsolvable systems of equations and proof complexity. In Proceedings of the International Congress of Mathematicians, Vol. III, Berlin, 451--460. https:\/\/www.emis.de\/journals\/DMJDMV\/xvolicm\/14\/Pitassi.MAN.html."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0246-0"},{"key":"e_1_2_1_86_1","first-page":"598","article-title":"Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function","volume":"41","author":"Razborov Alexander A.","year":"1987","unstructured":"Alexander A. Razborov . 1987 . Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function . Mat. Zametki 41 , 4 (1987), 598 -- 607 , 623. Alexander A. Razborov. 1987. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki 41, 4 (1987), 598--607, 623.","journal-title":"Mat. Zametki"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_88_1","volume-title":"Undergraduate Commutative Algebra","author":"Reid Miles","unstructured":"Miles Reid . 1995. Undergraduate Commutative Algebra . London Mathematical Society Student Texts, Vol . 29. Cambridge University Press , Cambridge. Miles Reid. 1995. Undergraduate Commutative Algebra. London Mathematical Society Student Texts, Vol. 29. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1203350879"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1974-0349648-2"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_93_1","volume-title":"Introduction to the Theory of Computation","author":"Sipser Michael","unstructured":"Michael Sipser . 2005. Introduction to the Theory of Computation ( second ed.). Course Technology . 431 pages. Michael Sipser. 2005. Introduction to the Theory of Computation (second ed.). Course Technology. 431 pages."},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.10.018"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0633"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436566"},{"key":"e_1_2_1_98_1","first-page":"184","article-title":"Vermeidung von Divisionen","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen . 1973 . Vermeidung von Divisionen . J. Reine Angew. Math. 264 (1973), 184 -- 202 . http:\/\/eudml.org\/doc\/151394. Volker Strassen. 1973. Vermeidung von Divisionen. J. Reine Angew. Math. 264 (1973), 184--202. http:\/\/eudml.org\/doc\/151394.","journal-title":"J. Reine Angew. Math."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_101_1","article-title":"Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE","author":"Toda Seinosuke","year":"1992","unstructured":"Seinosuke Toda . 1992 . Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Syst. E75D, 1 ( Jan. 1992), 116--124. Seinosuke Toda. 1992. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Syst. E75D, 1 (Jan. 1992), 116--124.","journal-title":"Trans. Inf. Syst. E75D, 1"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_104_1","first-page":"3","article-title":"Reducibility by algebraic projections","volume":"28","author":"Valiant Leslie G.","year":"1982","unstructured":"Leslie G. Valiant . 1982 . Reducibility by algebraic projections . Enseign. Math. 28 , 3 \u2013 4 (1982), 253--268. Leslie G. Valiant. 1982. Reducibility by algebraic projections. Enseign. Math. 28, 3\u20134 (1982), 253--268.","journal-title":"Enseign. Math."},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"key":"e_1_2_1_107_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Voevodsky Vladimir","year":"1998","unstructured":"Vladimir Voevodsky . 1998 . A1-homotopy theory . In Proceedings of the International Congress of Mathematicians , Vol. I . 579--604. https:\/\/www.emis.de\/journals\/DMJDMV\/xvolicm\/00\/Voevodsky.MAN.html. Vladimir Voevodsky. 1998. A1-homotopy theory. In Proceedings of the International Congress of Mathematicians, Vol. I. 579--604. https:\/\/www.emis.de\/journals\/DMJDMV\/xvolicm\/00\/Voevodsky.MAN.html."},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(87)80063-9"},{"key":"e_1_2_1_109_1","series-title":"Lecture Notes in Computer Science","volume-title":"Symbolic and Algebraic Computation, Edward W. Ng (Ed.)","author":"Zippel Richard","unstructured":"Richard Zippel . 1979. Probabilistic algorithms for sparse polynomials . In Symbolic and Algebraic Computation, Edward W. Ng (Ed.) . Lecture Notes in Computer Science , Vol. 72 . Springer , Berlin , 216--226. Richard Zippel. 1979. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, Edward W. Ng (Ed.). Lecture Notes in Computer Science, Vol. 72. Springer, Berlin, 216--226."},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230742","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230742","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230742","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:30Z","timestamp":1750208250000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230742"}},"subtitle":["The Ideal Proof System"],"short-title":[],"issued":{"date-parts":[[2018,11,26]]},"references-count":108,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3230742"],"URL":"https:\/\/doi.org\/10.1145\/3230742","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,26]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}