{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:58:03Z","timestamp":1781031483715,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":35,"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\/4.0\/legalcode"}],"funder":[{"name":"European Research Council (ERC)","award":["101002742"],"award-info":[{"award-number":["101002742"]}]},{"name":"Engineering and Physical Sciences Research Council (EPSRC)","award":["EP\/Z534158\/1"],"award-info":[{"award-number":["EP\/Z534158\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800721","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds against the Ideal Proof System in Finite Fields"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-9627-7251","authenticated-orcid":false,"given":"Tal","family":"Elbaz","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7191-9829","authenticated-orcid":false,"given":"Nashlen","family":"Govindasamy","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5978-720X","authenticated-orcid":false,"given":"Jiaqi","family":"Lu","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5558-9911","authenticated-orcid":false,"given":"Iddo","family":"Tzameret","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"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":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.21"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1374523"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.12"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520025"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2025.22"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689957"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.09.009"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Prerona Chatterjee Utsab Ghosal Partha Mukhopadhyay and Amit Sinhababu. 2025. IPS Lower Bounds for Formulas and Sum of ROABPs. CoRR abs\/2507.09515 doi:10.48550\/ARXIV.2507.09515 2507.09515. https:\/\/doi.org\/10.48550\/arXiv.2507.09515 10.48550\/arXiv.2507.09515","DOI":"10.48550\/ARXIV.2507.09515"},{"key":"e_1_3_2_1_10_1","first-page":"174","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","author":"Clegg Matthew","year":"1996","unstructured":"Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo. 1996. Using the Groebner basis algorithm to find proofs of unsatisfiability. ACM, In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996). 174-183."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16721-3"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/lipics.sat.2024.10"},{"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. 2506.17210. arxiv:2506.17210"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/lipics.ccc.2024.31"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2021.v017a010"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00025"},{"issue":"1","key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0304-3975(02)00446-2","article-title":"Algebraic proof systems over formulas. Logic and complexity in computer science (Cr\u00e9teil, 2001)","volume":"303","author":"Grigoriev Dima","year":"2003","unstructured":"Dima Grigoriev and Edward A. Hirsch. 2003. Algebraic proof systems over formulas. Logic and complexity in computer science (Cr\u00e9teil, 2001) Theoret. Comput. Sci., 303, 1, 83-102.","journal-title":"Theoret. Comput. Sci."},{"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 [cs.CC]."},{"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","unstructured":"Russell Impagliazzo Sasank Mouli and Toniann Pitassi. 2023. Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik Article 7 isbn:9783959772822 24 pages. CCC \u201923. doi:10.4230\/LIPIcs.CCC.2023.7 https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2023.7 10.4230\/LIPIcs.CCC.2023.7","DOI":"10.4230\/LIPIcs.CCC.2023.7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394754"},{"issue":"4","key":"e_1_3_2_1_23_1","first-page":"1424","article-title":"Characterizing Propositional Proofs as Noncommutative Formulas. In SIAM Journal on Computing","volume":"47","author":"Li Fu","year":"2018","unstructured":"Fu Li, Iddo Tzameret, and Zhengyu Wang. 2018. Characterizing Propositional Proofs as Noncommutative Formulas. In SIAM Journal on Computing. Full Version: 47, 4, 1424-1462.","journal-title":"Full Version"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3734215"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Fedor Part and Iddo Tzameret. 2021. Resolution with counting: dag-like lower bounds and different moduli. Comput. Complexity 30 1 Paper No. 2.71. doi:10.1007\/s00037-020-00202-x https:\/\/doi.org\/10.1007\/s00037-020-00202-x 10.1007\/s00037-020-00202-x","DOI":"10.1007\/s00037-020-00202-x"},{"key":"e_1_3_2_1_26_1","volume-title":"Descriptive complexity and finite models (Princeton, NJ","author":"Pitassi Toniann","year":"1996","unstructured":"Toniann Pitassi. 1997. Algebraic propositional proof systems. Amer. Math. Soc., In Descriptive complexity and finite models (Princeton, NJ, 1996) (DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 31). 215-244."},{"key":"e_1_3_2_1_27_1","first-page":"451","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, 1998). 451-460."},{"key":"e_1_3_2_1_28_1","first-page":"3","article-title":"Algebraic Proof Complexity: Progress, Frontiers and Challenges","volume":"3","author":"Pitassi Toniann","year":"2016","unstructured":"Toniann Pitassi and Iddo Tzameret. 2016. Algebraic Proof Complexity: Progress, Frontiers and Challenges. ACM. ACM SIGLOG News, 3, 3.","journal-title":"ACM. ACM SIGLOG News"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.04.001"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0246-0"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1447519"},{"key":"e_1_3_2_1_32_1","unstructured":"Ramprasad Saptharishi. 2016-2022. A survey of lower bounds in arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384288"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.07.004"}],"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.3800721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:33Z","timestamp":1781028273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":35,"alternative-id":["10.1145\/3798129.3800721","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800721","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"}}]}}