{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:53Z","timestamp":1781031413608,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CISE-2047756"],"award-info":[{"award-number":["CISE-2047756"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800865","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1569-1580","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6466-0476","authenticated-orcid":false,"given":"Joshua A.","family":"Grochow","sequence":"first","affiliation":[{"name":"University of Colorado Boulder, Departments of Computer Science and Mathematics, Boulder, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Yaroslav Alekseev Dima Grigoriev Edward A. Hirsch and Iddo Tzameret. 2019. Semi-Algebraic Proofs IPS Lower Bounds and the \u03c4 -Conjecture: Can a Natural Number be Negative? arxiv:1911.06738 Preprint of full version of AGHT","DOI":"10.1145\/3357713.3384245"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384245"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520025"},{"key":"e_1_3_2_1_4_1","volume-title":"Nutan Limaye, and Srikanth Srinivasan.","author":"Behera Amik Raj","year":"2026","unstructured":"Amik Raj Behera, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, and Srikanth Srinivasan. 2026. Separation Results for Constant-Depth and Multilinear Ideal Proof Systems. arxiv:2601.06299"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2025.22"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.645"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_1_13_1","unstructured":"Tal Elbaz Nashlen Govindasamy Jiaqi Lu and Iddo Tzameret. 2025. Lower Bounds against the Ideal Proof System in Finite Fields. arxiv:2506.17210"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2021.v017a010"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1958-10224-4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00025"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"e_1_3_2_1_18_1","unstructured":"Joshua A. Grochow. 2023. Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook\u2013Reckhow proof system. arxiv:2306.02184"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230742"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649616"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73020"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2012.519"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00044"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0019"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1082418532"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1107632"},{"key":"e_1_3_2_1_28_1","unstructured":"Dana Moshkovitz. 2010. An Alternative Proof of The Schwartz\u2013Zippel Lemma. https:\/\/eccc.weizmann.ac.il\/\/report\/2010\/096\/"},{"key":"e_1_3_2_1_29_1","unstructured":"\u00d8ystein Ore. 1922. \u00dcber h\u00f6here Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I."},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the DIMACS Workshop held at Princeton University","author":"Pitassi Toniann","year":"1996","unstructured":"Toniann Pitassi. 1996. Algebraic propositional proof systems. In Descriptive Complexity and Finite Models, Proceedings of the DIMACS Workshop held at Princeton University, Princeton, NJ, January 14\u2013\u201817, 1996. Edited by Neil Immerman and Phokion G. Kolaitis (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 31). American Mathematical Society, 215\u2013244."},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the International Congress of Mathematicians.","author":"Pitassi Toniann","year":"1998","unstructured":"Toniann Pitassi. 1998. Propositional proof complexity and unsolvability of polynomial equations. In Proceedings of the International Congress of Mathematicians. Vol. III. Sections 10\u201319. Held in Berlin, August 18-\u201327, 1998. 215\u2013244."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_3_2_1_33_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\u2013607, 623. issn:0025-567X English translation: Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333\u2013338, 1987.","journal-title":"Mat. Zametki"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451010"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800865","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:20Z","timestamp":1781027900000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":39,"alternative-id":["10.1145\/3798129.3800865","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800865","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}