{"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":1781031461017,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":49,"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":[{"name":"Polish National Science Centre","award":["2023\/51\/B\/ST6\/01505"],"award-info":[{"award-number":["2023\/51\/B\/ST6\/01505"]}]},{"name":"DFG","award":["462679611"],"award-info":[{"award-number":["462679611"]}]},{"name":"Miller Research Fellowship at the Miller Institute for Basic Research in Science, UC Berkeley","award":["None"],"award-info":[{"award-number":["None"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800854","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1453-1464","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2652-995X","authenticated-orcid":false,"given":"Bart\u0142omiej","family":"Dudek","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0909-3296","authenticated-orcid":false,"given":"Nick","family":"Fischer","sequence":"additional","affiliation":[{"name":"MPI-INF, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7500-6848","authenticated-orcid":false,"given":"Geri","family":"Gokaj","sequence":"additional","affiliation":[{"name":"KIT, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5264-1772","authenticated-orcid":false,"given":"Ce","family":"Jin","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4813-4852","authenticated-orcid":false,"given":"Marvin","family":"K\u00fcnnemann","sequence":"additional","affiliation":[{"name":"KIT, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1224-9730","authenticated-orcid":false,"given":"Xiao","family":"Mao","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7509-1686","authenticated-orcid":false,"given":"Mirza","family":"Red\u017ei\u0107","sequence":"additional","affiliation":[{"name":"KIT, Karlsruhe, Germany"}],"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.1145\/3188745.3188938"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520066"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649696"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.63"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1388"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.IPEC.2021.3"},{"key":"e_1_3_2_1_8_1","first-page":"487","article-title":"On economical construction of the transitive closure of an oriented graph","volume":"194","author":"Arlazarov Vladimir L.","year":"1970","unstructured":"Vladimir L. Arlazarov, Yefim A. Dinic, Aleksandr Kronrod, and Igor Aleksandrovich Farad\u017eev. 1970. On economical construction of the transitive closure of an oriented graph. In Doklady Akademii Nauk. 194, 487\u2013488.","journal-title":"Doklady Akademii Nauk."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2022.V018A016"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2012.V008A004"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.GS.2013.005"},{"key":"e_1_3_2_1_13_1","volume-title":"Bloom and Olof Sisask","author":"Thomas","year":"2023","unstructured":"Thomas F. Bloom and Olof Sisask. 2023. An improvement to the Kelley-Meka bounds on three-term arithmetic progressions. arXiv, arxiv:2309.02353"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2019.31"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2021.40"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387662"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.16"},{"key":"e_1_3_2_1_18_1","volume-title":"The algebraic theory of semigroups","author":"Clifford Alfred H","year":"1961","unstructured":"Alfred H Clifford and Gordon B Preston. 1961. The algebraic theory of semigroups, vol. 1. American Mathematical Society, Providence, 2, 7 (1961)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2017.22"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00057"},{"key":"e_1_3_2_1_21_1","volume-title":"Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection. arxiv:2603.28843. arxiv:2603.28843","author":"Dudek Bart\u0142omiej","year":"2026","unstructured":"Bart\u0142omiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin K\u00fcnnemann, Xiao Mao, and Mirza Red\u017ei\u0107. 2026. Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection. arxiv:2603.28843. arxiv:2603.28843"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00126"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2025.78"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2025.81"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2025.55"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2025.42"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SOCG.2023.36"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1112\/s0025579317000316"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585157"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649721"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00059"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00059"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2020.27"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.124"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2017.21"},{"key":"e_1_3_2_1_39_1","unstructured":"James Leng Ashwin Sah and Mehtaab Sawhney. 2024. Improved Bounds for Szemer\u00e9di\u2019s Theorem. arXiv arxiv:2402.17995"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_3_2_1_41_1","unstructured":"Adam Polak. 2025. Personal communication"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325387"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2010.V006A007"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755149"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250876"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.006"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585163"}],"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.3800854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:27Z","timestamp":1781028327000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":49,"alternative-id":["10.1145\/3798129.3800854","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800854","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"}}]}}