{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:41Z","timestamp":1781031461052,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":71,"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":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["101002742"],"award-info":[{"award-number":["101002742"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/Z534158\/1"],"award-info":[{"award-number":["EP\/Z534158\/1"]}],"id":[{"id":"10.13039\/501100000266","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.3800735","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"138-149","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Weak Rank Principle: Lower Bounds and Applications"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8125-199X","authenticated-orcid":false,"given":"Michal","family":"Garl\u00edk","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5648-8194","authenticated-orcid":false,"given":"Svyatoslav","family":"Gryaznov","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7632-7574","authenticated-orcid":false,"given":"Hanlin","family":"Ren","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study at Princeton, Princeton, USA"}],"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.1007\/BF01302964"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389944"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959893"},{"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.4230\/LIPIcs.CCC.2019.24"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2023.31"},{"key":"e_1_3_2_1_7_1","volume-title":"Linear algebra methods in combinatorics. Department of Computer Science","author":"Babai L\u00e1szl\u00f3","unstructured":"L\u00e1szl\u00f3 Babai and P\u00e9ter Frankl. 1992. Linear algebra methods in combinatorics. Department of Computer Science, Univ. of Chicago."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1998.1575"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-010-0293-1"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_3"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273826"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2000.1726"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00040"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511676277"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_3_2_1_17_1","first-page":"331","article-title":"Progression-free sets in Z_4^n are exponentially small","author":"Croot Ernie","year":"2017","unstructured":"Ernie Croot, Vsevolod F Lev, and P\u00e9ter P\u00e1l Pach. 2017. Progression-free sets in Z_4^n are exponentially small. Annals of Mathematics, 331\u2013337.","journal-title":"Annals of Mathematics"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-012-0049-1"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2009.01.002"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.46298\/THEORETICS.25.9"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00607-3"},{"key":"e_1_3_2_1_22_1","first-page":"339","article-title":"On large subsets of F^n_q with no three-term arithmetic progression","author":"Ellenberg Jordan S","year":"2017","unstructured":"Jordan S Ellenberg and Dion Gijswijt. 2017. On large subsets of F^n_q with no three-term arithmetic progression. Annals of Mathematics, 339\u2013343.","journal-title":"Annals of Mathematics"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2023.4"},{"key":"e_1_3_2_1_24_1","unstructured":"Michal Garl\u00edk Svyatoslav Gryaznov Hanlin Ren and Iddo Tzameret. 2026. The Weak Rank Principle: Lower Bounds and Applications. https:\/\/symplectic.imperial.ac.uk\/viewobject.html?cid=1&id=1653030"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230742"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3425606"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/130917788"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2019.190.3.6"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/S000370050024"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959894"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102722"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2003.12.003"},{"key":"e_1_3_2_1_36_1","volume-title":"Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation","author":"Je\u0159\u00e1bek Emil","unstructured":"Emil Je\u0159\u00e1bek. 2005. Weak pigeonhole principle, and randomized computation. Ph. D. Dissertation. Faculty of Mathematics and Physics, Charles University, Prague."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2178\/JSL\/1191333850"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00153-024-00938-1"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.17"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.2178\/JSL\/1080938841"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00ed\u010dek. 2019. Proof Complexity. Cambridge University Press. isbn:9781108416849 lccn:2018042527 https:\/\/books.google.co.uk\/books?id=uOyKuQEACAAJ","DOI":"10.1017\/9781108242066"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"e_1_3_2_1_45_1","volume-title":"Proc. from the 13th International Congress of Logic, Methodology and Philosophy of Science","author":"Kraj\u00ed\u010dek Jan","year":"2009","unstructured":"Jan Kraj\u00ed\u010dek. 2009. A proof complexity generator. In Proc. from the 13th International Congress of Logic, Methodology and Philosophy of Science (Beijing, August 2007) (Studies in Logic and the Foundations of Mathematics). King\u2019s College Publications, London."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009611664"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2002.1830"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3675668"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2019.102735"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028061"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-020-00202-x"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897637"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972640"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2008.04.001"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/S000370050013"},{"key":"e_1_3_2_1_60_1","volume-title":"TR01","author":"Razborov Alexander A.","year":"2001","unstructured":"Alexander A. Razborov. 2001. Improved Resolution Lower Bounds for the Weak Pigeonhole Principle. Electron. Colloquium Comput. Complex., TR01 (2001), Article TR01-055, ECCC:TR01-055. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2001\/TR01-055\/index.html"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46011-X_8"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2004.01.004"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.2.1"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.15"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2003.10.018"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00153-003-0205-Z"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(02)00038-6"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3431922"},{"key":"e_1_3_2_1_71_1","unstructured":"A. Woods. 1981. Some problems in logic and number theory and their connections. University of Manchester. 14"}],"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.3800735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:19Z","timestamp":1781028319000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":71,"alternative-id":["10.1145\/3798129.3800735","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800735","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"}}]}}