{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:03Z","timestamp":1750695003361,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","funder":[{"name":"Knut och Alice Wallenbergs Stiftelse","award":["2021.0307"],"award-info":[{"award-number":["2021.0307"]}]},{"name":"Vetenskapsr\u00e5det","award":["2021-05104,2016-00782"],"award-info":[{"award-number":["2021-05104,2016-00782"]}]},{"name":"Danmarks Frie Forskningsfond","award":["9040-00389B"],"award-info":[{"award-number":["9040-00389B"]}]},{"name":"HORIZON EUROPE Marie Sklodowska-Curie Actions","award":["101146273"],"award-info":[{"award-number":["101146273"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718271","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1371-1382","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler\u2013Leman"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8923-1240","authenticated-orcid":false,"given":"Susanna F.","family":"de Rezende","sequence":"first","affiliation":[{"name":"Lund University, Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8636-1290","authenticated-orcid":false,"given":"Noah","family":"Fleming","sequence":"additional","affiliation":[{"name":"Memorial University of Newfoundland, St. John's, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7279-807X","authenticated-orcid":false,"given":"Duri Andrea","family":"Janett","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"},{"name":"Lund University, Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2700-4285","authenticated-orcid":false,"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"},{"name":"Lund University, Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5652-9737","authenticated-orcid":false,"given":"Shuo","family":"Pang","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_3_2_1_2_1","first-page":"530","article-title":"On a Method for Obtaining Lower Bounds for the Complexity of Individual Monotone Functions","volume":"31","author":"Andreev Alexander E.","year":"1985","unstructured":"Alexander E. Andreev. 1985. On a Method for Obtaining Lower Bounds for the Complexity of Individual Monotone Functions. Soviet Mathematics Doklady, 31, 3 (1985), 530\u2013534. English translation of a paper in Doklady Akademii Nauk SSSR","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914085"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.10"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806703"},{"key":"e_1_3_2_1_7_1","first-page":"66","article-title":"Propositional Proof Complexity: Past, Present, and Future","volume":"65","author":"Beame Paul","year":"1998","unstructured":"Paul Beame and Toniann Pitassi. 1998. Propositional Proof Complexity: Past, Present, and Future. Bulletin of the European Association for Theoretical Computer Science, 65 (1998), June, 66\u201389.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488711"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.48"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Christoph Berkholz Moritz Lichter and Harry Vinall-Smeeth. 2024. Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism. arXiv preprint 2407.17947 July https:\/\/doi.org\/10.48550\/arXiv.2407.17947 10.48550\/arXiv.2407.17947","DOI":"10.48550\/arXiv.2407.17947"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1109072"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3195257"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275569"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a004"},{"key":"e_1_3_2_1_15_1","unstructured":"Sam Buss and Neil Thapen. 2024. A Simple Supercritical Tradeoff between Size and Height in Resolution. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2024\/001\/"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA200990"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_18_1","unstructured":"Arkadev Chattopadhyay and Pavel Dvo\u0159\u00e1k. 2024. Super-critical Trade-offs in Resolution over Parities Via Lifting. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2024\/132\/"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.34"},{"key":"e_1_3_2_1_21_1","volume-title":"Jakob Nordstr\u00f6m, and Shuo Pang.","author":"de Rezende Susanna F.","year":"2024","unstructured":"Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordstr\u00f6m, and Shuo Pang. 2024. Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler\u2013Leman. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2024\/185\/"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4842-8_26"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3486680"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-71430-7_18"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.70"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_27"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370100001"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3378667"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a013"},{"key":"e_1_3_2_1_31_1","unstructured":"Mika G\u00f6\u00f6s Gilbert Maystre Kilian Risse and Dmitry Sokolov. 2024. Supercritical Tradeoffs for Monotone Circuits. Electronic Colloquium on Computational Complexity (ECCC). https:\/\/eccc.weizmann.ac.il\/report\/2024\/186\/ To appear in STOC \u201925"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470677"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS56636.2023.10175741"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00052"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.20"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436980.3436982"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(2:19)2019"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof Complexity (Encyclopedia of Mathematics and Its Applications Vol. 170). Cambridge University Press. https:\/\/doi.org\/10.1017\/9781108242066 10.1017\/9781108242066","DOI":"10.1017\/9781108242066"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/lics.2019.8785694"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.104"},{"key":"e_1_3_2_1_44_1","first-page":"1","article-title":"Weisfeiler and Leman go Machine Learning: The Story so far","volume":"24","author":"Morris Christopher","year":"2023","unstructured":"Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. 2023. Weisfeiler and Leman go Machine Learning: The Story so far. Journal of Machine Learning Research, 24, 333 (2023), 1\u201359. http:\/\/jmlr.org\/papers\/v24\/22-0240.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2010.30"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_3_2_1_49_1","first-page":"354","article-title":"Lower Bounds for the Monotone Complexity of Some Boolean Functions","volume":"31","author":"Razborov Alexander A.","year":"1985","unstructured":"Alexander A. Razborov. 1985. Lower Bounds for the Monotone Complexity of Some Boolean Functions. Soviet Mathematics Doklady, 31, 2 (1985), 354\u2013357. English translation of a paper in Doklady Akademii Nauk SSSR","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122698"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1070\/IM1995v059n01ABEH000009"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858790"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0840"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-017-0163-1"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58747-9_26"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649636"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-81955-1_28"},{"key":"e_1_3_2_1_59_1","first-page":"12","article-title":"A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya","volume":"2","author":"Weisfeiler Boris","year":"1968","unstructured":"Boris Weisfeiler and Andrei Leman. 1968. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya, Ser. 2, 9 (1968), 12\u201316. English translation by Grigory Ryabov available at https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf","journal-title":"Ser."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:47:33Z","timestamp":1750693653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":59,"alternative-id":["10.1145\/3717823.3718271","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718271","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}