{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:53Z","timestamp":1781031413524,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":43,"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","first-page":"5585","volume-title":"Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026","author":"Assadi Sepehr","unstructured":"Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Mart\u00edn Costa, Shay Solomon, and Tianyi Zhang. Vizing\u2019s theorem in deterministic almost-linear time. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, pages 5558\u20135585. 2026."},{"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","first-page":"16","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"107","author":"Arar Moab","year":"2018","unstructured":"Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018, volume 107 of LIPIcs, pages 7:1\u20137:16, 2018."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.96"},{"key":"e_1_3_2_1_7_1","volume-title":"The stochastic matching problem with (very) few queries. ACM Transactions on Economics and Computation (TEAC), 7(3):1\u201319","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\u201319, 2019."},{"key":"e_1_3_2_1_8_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":"Bernstein Aaron","year":"2026","unstructured":"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_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718153"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451113"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch6"},{"key":"e_1_3_2_1_14_1","volume-title":"A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms (TALG), 17(4):1\u201351","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\u201351, 2021."},{"key":"e_1_3_2_1_15_1","first-page":"327","volume-title":"2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Behnezhad Soheil","unstructured":"Soheil Behnezhad and Alma Ghafari. Fully dynamic matching and ordered ruzsa-szemer\u00e9di graphs. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 314\u2013327. IEEE, 2024."},{"key":"e_1_3_2_1_16_1","volume-title":"Fully dynamic (\u03b4+ 1)-coloring in o (1) update time. ACM Transactions On Algorithms (TALG), 18(2):1\u201325","author":"Bhattacharya Sayan","year":"2022","unstructured":"Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C Liu, and Shay Solomon. Fully dynamic (\u03b4+ 1)-coloring in o (1) update time. ACM Transactions On Algorithms (TALG), 18(2):1\u201325, 2022."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106158"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998925"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.140"},{"key":"e_1_3_2_1_22_1","first-page":"1588","volume-title":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Bhattacharya Sayan","unstructured":"Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Dynamic (1+\u220a)-approximate matching size in truly sublinear update time. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1563\u20131588. IEEE, 2023."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3679009"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649648"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.169"},{"key":"e_1_3_2_1_26_1","volume-title":"Springer","author":"Bernstein Aaron","year":"2015","unstructured":"Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In International Colloquium on Automata, Languages, and Programming, pages 167\u2013179. Springer, 2015."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"key":"e_1_3_2_1_29_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_30_1","first-page":"21","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\u201379:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2025."},{"key":"e_1_3_2_1_31_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_32_1","first-page":"557","volume-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Gupta Manoj","unstructured":"Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 548\u2013557. IEEE, 2013."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.2"},{"key":"e_1_3_2_1_34_1","volume-title":"Constant-time dynamic (\u03b4+ 1)-coloring. ACM Transactions on Algorithms (TALG), 18(2):1\u201321","author":"Henzinger Monika","year":"2022","unstructured":"Monika Henzinger and Pan Peng. Constant-time dynamic (\u03b4+ 1)-coloring. ACM Transactions on Algorithms (TALG), 18(2):1\u201321, 2022."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57899-4_44"},{"key":"e_1_3_2_1_36_1","first-page":"21","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\u201394:21, 2022."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00006"},{"key":"e_1_3_2_1_38_1","volume-title":"Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):1\u201315","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\u201315, 2015."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_40_1","series-title":"LIPIcs","first-page":"23","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\u2013111:23, 2022."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_1_42_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\u201330, 1964.","journal-title":"Diskret analiz"},{"key":"e_1_3_2_1_43_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,9]],"date-time":"2026-06-09T17:58:00Z","timestamp":1781027880000},"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":43,"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"}}]}}