{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:58:25Z","timestamp":1781218705939,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":41,"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\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2402284"],"award-info":[{"award-number":["CCF-2402284"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2402283"],"award-info":[{"award-number":["CCF-2402283"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["HDR TRIPODS 2216899"],"award-info":[{"award-number":["HDR TRIPODS 2216899"]}],"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.3800868","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1604-1615","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7839-751X","authenticated-orcid":false,"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2601-1689","authenticated-orcid":false,"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"New York University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4554-9033","authenticated-orcid":false,"given":"Junkai","family":"Song","sequence":"additional","affiliation":[{"name":"New York University, New York, 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":"publisher","DOI":"10.1145\/3717823.3718265"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978971.198"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585110"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.109"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.96"},{"key":"e_1_3_2_1_6_1","volume-title":"The stochastic matching problem with (very) few queries. ACM Transactions on Economics and Computation (TEAC), 7(3):1-19","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with (very) few queries. ACM Transactions on Economics and Computation (TEAC), 7(3):1-19, 2019."},{"key":"e_1_3_2_1_7_1","volume-title":"Separations between oblivious and adaptive adversaries for natural dynamic graph problems. In to appear in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Aaron Bernstein BBF","year":"2026","unstructured":"BBF + 26] Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, and Thatchaphol Saranurak. Separations between oblivious and adaptive adversaries for natural dynamic graph problems. In to appear in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718153"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451113"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch6"},{"key":"e_1_3_2_1_13_1","volume-title":"A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms (TALG), 17(4):1-51","author":"Bernstein Aaron","year":"2021","unstructured":"Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms (TALG), 17(4):1-51, 2021."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00027"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106158"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998925"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.140"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00095"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3679009"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649648"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.169"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"key":"e_1_3_2_1_27_1","volume-title":"Improved algorithms for fully dynamic maximal independent set","author":"Du Yuhao","year":"2018","unstructured":"Yuhao Du and Hengjie Zhang. Improved algorithms for fully dynamic maximal independent set, 2018."},{"key":"e_1_3_2_1_28_1","first-page":"1","volume-title":"52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025","volume":"334","author":"Flin Maxime","year":"2025","unstructured":"Maxime Flin and Magn\u00fas M. Halld\u00f3rsson. Faster dynamic (\u0394+1)-coloring against adaptive adversaries. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, volume 334 of LIPIcs, pages 79:1-79:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2025."},{"key":"e_1_3_2_1_29_1","volume-title":"Simple dynamic algorithms for maximal independent set and other problems","author":"Gupta Manoj","year":"2018","unstructured":"Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set and other problems, 2018."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.2"},{"key":"e_1_3_2_1_32_1","volume-title":"Constant-time dynamic (\ud835\udeff+ 1)-coloring. ACM Transactions on Algorithms (TALG), 18(2):1-21","author":"Henzinger Monika","year":"2022","unstructured":"Monika Henzinger and Pan Peng. Constant-time dynamic (\ud835\udeff+ 1)-coloring. ACM Transactions on Algorithms (TALG), 18(2):1-21, 2022."},{"key":"e_1_3_2_1_33_1","first-page":"99","volume-title":"International Workshop on Graph-Theoretic Concepts in Computer Science","author":"Ivkovi\u0107 Zoran","year":"1993","unstructured":"Zoran Ivkovi\u0107 and Errol L Lloyd. Fully dynamic maintenance of vertex cover. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 99-111. Springer, 1993."},{"key":"e_1_3_2_1_34_1","first-page":"1","volume-title":"13th Innovations in Theoretical Computer Science Conference, ITCS 2022","volume":"215","author":"Kiss Peter","year":"2022","unstructured":"Peter Kiss. Deterministic dynamic matching in worst-case update time. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, pages 94:1-94:21, 2022."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00006"},{"key":"e_1_3_2_1_36_1","volume-title":"Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):1-15","author":"Neiman Ofer","year":"2015","unstructured":"Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):1-15, 2015."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_38_1","series-title":"LIPIcs","first-page":"1","volume-title":"13th Innovations in Theoretical Computer Science Conference, ITCS","author":"Roghani Mohammad","year":"2022","unstructured":"Mohammad Roghani, Amin Saberi, and David Wajc. Beating the folklore algorithm for dynamic matching. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Berkeley, CA, USA, January 31 - February 3, 2022, volume 215 of LIPIcs, pages 111:1-111:23, 2022."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_1_40_1","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing Vadim G","year":"1964","unstructured":"Vadim G Vizing. On an estimate of the chromatic class of a p-graph. Diskret analiz, 3:25-30, 1964.","journal-title":"Diskret analiz"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384258"}],"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.3800868","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800868","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:30:51Z","timestamp":1781217051000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":41,"alternative-id":["10.1145\/3798129.3800868","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800868","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"}}]}}