{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:58Z","timestamp":1781077678322,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":71,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1910588, CCF-1814603, CCF-1750808, CCF-1618280, CCF-1527110"],"award-info":[{"award-number":["CCF-1910588, CCF-1814603, CCF-1750808, CCF-1618280, CCF-1527110"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384258","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"page":"194-207","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Rounding dynamic matchings against an adaptive adversary"],"prefix":"10.1145","author":[{"given":"David","family":"Wajc","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_3_1","first-page":"7","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Arar Moab","year":"2018","unstructured":"Moab Arar , Shiri Chechik , Sarel Cohen , Clif Stein , and David Wajc . Dynamic matching : Reducing integral algorithms to approximately-maximal fractional algorithms . In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP) , pages 7 : 1-7 : 16, 2018 . Moab Arar, Shiri Chechik, Sarel Cohen, Clif Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pages 7 : 1-7 : 16, 2018."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA)","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi and Aaron Bernstein . Towards a unified theory of sparsification for matching problems . In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA) , 2019 . Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA), 2019."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940769"},{"key":"e_1_3_2_1_6_1","first-page":"333","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML)","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi , Mohammadhossein Bateni , and Vahab Mirrokni . Distributed weighted matching via randomized composable coresets . In Proceedings of the 36th International Conference on Machine Learning (ICML) , pages 333 - 343 , 2019 . Sepehr Assadi, Mohammadhossein Bateni, and Vahab Mirrokni. Distributed weighted matching via randomized composable coresets. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 333-343, 2019."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_1_8_1","volume-title":"Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8 ( 4 ): 35","author":"Baswana Surender","year":"2012","unstructured":"Surender Baswana , Sumeet Khurana , and Soumojit Sarkar . Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8 ( 4 ): 35 , 2012 . Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8 ( 4 ): 35, 2012."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.152"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Bernstein Aaron","year":"2017","unstructured":"Aaron Bernstein . Deterministic partially dynamic single source shortest paths in weighted graphs . In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP) , 2017 . Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP), 2017."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.29"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310550"},{"key":"e_1_3_2_1_16_1","volume-title":"SCC, and shortest paths via directed expanders and congestion balancing. Unpublished manuscript","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein , Maximillian Probst Gutenberg, and Thatchaphol Sarankurak. Deterministic decremental reachability , SCC, and shortest paths via directed expanders and congestion balancing. Unpublished manuscript , 2020 . Aaron Bernstein, Maximillian Probst Gutenberg, and Thatchaphol Sarankurak. Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing. Unpublished manuscript, 2020."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.113"},{"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.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.30"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.1"},{"key":"e_1_3_2_1_22_1","first-page":"219","volume":"261","author":"Bhattacharya Sayan","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Giuseppe Italiano . Dynamic algorithms via the primal-dual method. Information and Computation , 261 : 219 - 239 , 2018. Sayan Bhattacharya, Monika Henzinger, and Giuseppe Italiano. Dynamic algorithms via the primal-dual method. Information and Computation, 261 : 219-239, 2018.","journal-title":"Computation"},{"key":"e_1_3_2_1_23_1","series-title":"SIAM Journal on Computing (SICOMP), 47 ( 3 ): 859-887","volume-title":"Deterministic fully dynamic data structures for vertex cover and matching","author":"Bhattacharya Sayan","year":"2018","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Giuseppe F Italiano . Deterministic fully dynamic data structures for vertex cover and matching . SIAM Journal on Computing (SICOMP), 47 ( 3 ): 859-887 , 2018 . Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing (SICOMP), 47 ( 3 ): 859-887, 2018."},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Charikar Moses","year":"2018","unstructured":"Moses Charikar and Shay Solomon . Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds . In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP) , 2018 . Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), 2018."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_26_1","volume-title":"On dynamic shortest paths with adaptive adversary. Unpublished manuscript","author":"Chuzhoy Julia","year":"2019","unstructured":"Julia Chuzhoy and Thatchaphol Saranurak . On dynamic shortest paths with adaptive adversary. Unpublished manuscript , 2019 . Julia Chuzhoy and Thatchaphol Saranurak. On dynamic shortest paths with adaptive adversary. Unpublished manuscript, 2019."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.62"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00010"},{"key":"e_1_3_2_1_29_1","first-page":"48","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP)","author":"Dahlgaard S\u00f8ren","year":"2016","unstructured":"S\u00f8ren Dahlgaard . On the hardness of partially dynamic graph problems and connections to diameter . In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP) , pages 48 : 1-48 : 14, 2016 . S\u00f8ren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 48 : 1-48 : 14, 2016."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.117"},{"key":"e_1_3_2_1_31_1","volume-title":"Balls and bins: A study in negative dependence. BRICS Report Series, 3 ( 25 )","author":"Dubhashi Devdatt","year":"1996","unstructured":"Devdatt Dubhashi and Desh Ranjan . Balls and bins: A study in negative dependence. BRICS Report Series, 3 ( 25 ) , 1996 . Devdatt Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3 ( 25 ), 1996."},{"key":"e_1_3_2_1_32_1","volume-title":"Sparsiifcation-a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44 ( 5 ): 669-696","author":"Eppstein David","year":"1997","unstructured":"David Eppstein , Zvi Galil , Giuseppe F Italiano , and Amnon Nissenzweig . Sparsiifcation-a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44 ( 5 ): 669-696 , 1997 . David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig. Sparsiifcation-a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44 ( 5 ): 669-696, 1997."},{"key":"e_1_3_2_1_33_1","first-page":"505","volume":"13","author":"Fleischer Lisa K","unstructured":"Lisa K Fleischer . Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics , 13 ( 4 ): 505 - 520 , 2000. Lisa K Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13 ( 4 ): 505-520, 2000.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_2_1_34_1","first-page":"377","volume-title":"Dynamic low-stretch trees via dynamic low-diameter decompositions","author":"Forster Sebastian","year":"2019","unstructured":"Sebastian Forster and Gramoz Goranci . Dynamic low-stretch trees via dynamic low-diameter decompositions . pages 377 - 388 , 2019 . Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. pages 377-388, 2019."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_3_2_1_36_1","series-title":"SIAM Journal on Computing (SICOMP), 37 ( 2 ): 630-652","volume-title":"Faster and simpler algorithms for multicommodity flow and other fractional packing problems","author":"Garg Naveen","year":"2007","unstructured":"Naveen Garg and Jochen Koenemann . Faster and simpler algorithms for multicommodity flow and other fractional packing problems . SIAM Journal on Computing (SICOMP), 37 ( 2 ): 630-652 , 2007 . Naveen Garg and Jochen Koenemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing (SICOMP), 37 ( 2 ): 630-652, 2007."},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA)","author":"Ghafari Mohsen","year":"2019","unstructured":"Mohsen Ghafari and David Wajc . Simplified and space-optimal semi-streaming (2 + )-approximate matching . In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA) , 2019 . Mohsen Ghafari and David Wajc. Simplified and space-optimal semi-streaming (2 + )-approximate matching. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA), 2019."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095157"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055493"},{"key":"e_1_3_2_1_41_1","first-page":"548","volume-title":"Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS)","author":"Gupta Manoj","year":"2013","unstructured":"Manoj Gupta and Richard Peng . Fully dynamic ( 1 + )-approximate matchings. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS) , pages 548 - 557 , 2013 . Manoj Gupta and Richard Peng. Fully dynamic ( 1 + )-approximate matchings. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 548-557, 2013."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.155"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.154"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_45_1","series-title":"SIAM Journal on Computing (SICOMP), 45 ( 3 ): 947-1006","volume-title":"Dynamic approximate all-pairs shortest paths: Breaking the () barrier and derandomization","author":"Henzinger Monika","year":"2016","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . Dynamic approximate all-pairs shortest paths: Breaking the () barrier and derandomization . SIAM Journal on Computing (SICOMP), 45 ( 3 ): 947-1006 , 2016 . Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the () barrier and derandomization. SIAM Journal on Computing (SICOMP), 45 ( 3 ): 947-1006, 2016."},{"key":"e_1_3_2_1_46_1","volume-title":"Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM (JACM), 46 ( 4 ): 502-516","author":"Henzinger Monika R","year":"1999","unstructured":"Monika R Henzinger and Valerie King . Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM (JACM), 46 ( 4 ): 502-516 , 1999 . Monika R Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM (JACM), 46 ( 4 ): 502-516, 1999."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Jacob Holm Kristian De Lichtenberg and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity minimum spanning tree 2-edge and biconnectivity. Journal of the ACM (JACM) 48 ( 4 ): 723-760 2001.  Jacob Holm Kristian De Lichtenberg and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity minimum spanning tree 2-edge and biconnectivity. Journal of the ACM (JACM) 48 ( 4 ): 723-760 2001.","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_48_1","volume-title":"SIAM Journal on computing, 2 ( 4 ): 225-231","author":"Hopcroft John E","year":"1973","unstructured":"John E Hopcroft and Richard M Karp . An 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2 ( 4 ): 225-231 , 1973 . John E Hopcroft and Richard M Karp. An 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2 ( 4 ): 225-231, 1973."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/647674.731515"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176346079"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627898"},{"key":"e_1_3_2_1_52_1","first-page":"1183","volume":"10","author":"Khursheed Alam","unstructured":"Alam Khursheed and KM Lai Saxena . Positive dependence in multivariate distributions. Communications in Statistics-Theory and Methods , 10 ( 12 ): 1183 - 1196 , 1981. Alam Khursheed and KM Lai Saxena. Positive dependence in multivariate distributions. Communications in Statistics-Theory and Methods, 10 ( 12 ): 1183-1196, 1981.","journal-title":"Methods"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_29"},{"key":"e_1_3_2_1_55_1","volume-title":"Improved distributed approximate matching. Journal of the ACM (JACM), 62 ( 5 ): 38","author":"Lotker Zvi","year":"2015","unstructured":"Zvi Lotker , Boaz Patt-Shamir , and Seth Pettie . Improved distributed approximate matching. Journal of the ACM (JACM), 62 ( 5 ): 38 , 2015 . Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching. Journal of the ACM (JACM), 62 ( 5 ): 38, 2015."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_3_2_1_57_1","first-page":"121","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC)","author":"M\u0105dry Aleksander","year":"2010","unstructured":"Aleksander M\u0105dry . Faster approximation schemes for fractional multicommodity lfow problems via dynamic graph algorithms . In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC) , pages 121 - 130 , 2010 . Aleksander M\u0105dry. Faster approximation schemes for fractional multicommodity lfow problems via dynamic graph algorithms. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 121-130, 2010."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_59_1","volume-title":"Proceedings of the 58","author":"Nanongkai Danupon","unstructured":"Danupon Nanongkai , Thatchaphol Saranurak , and Christian Wulf-Nilsen . Dynamic minimum spanning forest with subpolynomial worst-case update time . In Proceedings of the 58 . Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulf-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In Proceedings of the 58."},{"key":"e_1_3_2_1_60_1","volume-title":"Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12 ( 1 ): 7","author":"Neiman Ofer","year":"2016","unstructured":"Ofer Neiman and Shay Solomon . Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12 ( 1 ): 7 , 2016 . Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12 ( 1 ): 7, 2016."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_62_1","volume-title":"ACM Transactions on Algorithms (TALG), 15 ( 2 ): 18","author":"Paz Ami","year":"2018","unstructured":"Ami Paz and Gregory Schwartzman . A ( 2 + )-approximation for maximum weight matching in the semi-streaming model. ACM Transactions on Algorithms (TALG), 15 ( 2 ): 18 , 2018 . Ami Paz and Gregory Schwartzman. A ( 2 + )-approximation for maximum weight matching in the semi-streaming model. ACM Transactions on Algorithms (TALG), 15 ( 2 ): 18, 2018."},{"key":"e_1_3_2_1_63_1","first-page":"712","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Peleg David","year":"2016","unstructured":"David Peleg and Shay Solomon . Dynamic ( 1 + )-approximate matchings : a density-sensitive approach . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 712 - 729 , 2016 . David Peleg and Shay Solomon. Dynamic ( 1 + )-approximate matchings: a density-sensitive approach. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712-729, 2016."},{"key":"e_1_3_2_1_64_1","first-page":"118","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sankowski Piotr","year":"2007","unstructured":"Piotr Sankowski . Faster dynamic matchings and vertex connectivity . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 118 - 126 , 2007 . Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 118-126, 2007."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_1_66_1","first-page":"52","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Solomon Shay","year":"2018","unstructured":"Shay Solomon . Local algorithms for bounded degree sparsifiers in sparse graphs . In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS) , pages 52 : 1-52 : 19, 2018 . Shay Solomon. Local algorithms for bounded degree sparsifiers in sparse graphs. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS), pages 52 : 1-52 : 19, 2018."},{"key":"e_1_3_2_1_67_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Stubbs Daniel","year":"2017","unstructured":"Daniel Stubbs and Virginia Vassilevska Williams . Metatheorems for dynamic weighted matching . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS) , 2017 . Daniel Stubbs and Virginia Vassilevska Williams. Metatheorems for dynamic weighted matching. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335345"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00036"},{"key":"e_1_3_2_1_70_1","volume-title":"On an estimate of the chromatic class of a p-graph. Diskret analiz, 3 : 25-30","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 . Vadim G Vizing. On an estimate of the chromatic class of a p-graph. Diskret analiz, 3 : 25-30, 1964."},{"key":"e_1_3_2_1_71_1","volume-title":"Rounding dynamic matchings against an adaptive adversary. arXiv preprint arXiv:1911.05545","author":"Wajc David","year":"2019","unstructured":"David Wajc . Rounding dynamic matchings against an adaptive adversary. arXiv preprint arXiv:1911.05545 , 2019 . David Wajc. Rounding dynamic matchings against an adaptive adversary. arXiv preprint arXiv:1911.05545, 2019."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384258","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":71,"alternative-id":["10.1145\/3357713.3384258","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384258","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}