{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,6]],"date-time":"2022-07-06T10:56:23Z","timestamp":1657104983006},"publisher-location":"New York, NY, USA","reference-count":71,"publisher":"ACM","funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1910588, CCF-1814603, CCF-1750808, CCF-1618280, CCF-1527110"]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher"}],"content-domain":{"domain":[],"crossmark-restriction":false},"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},"source":"Crossref","is-referenced-by-count":4,"title":["Rounding dynamic matchings against an adaptive adversary"],"prefix":"10.1145","author":[{"given":"David","family":"Wajc","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"477","volume-title":"Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS)","author":"Abboud Amir","year":"2016"},{"key":"e_1_3_2_1_2_1","first-page":"434","volume-title":"Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS)","author":"Abboud Amir","year":"2014"},{"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"},{"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"},{"key":"e_1_3_2_1_5_1","first-page":"43","volume-title":"Proceedings of the 17th ACM Conference on Economics and Computation (EC)","author":"Assadi Sepehr","year":"2016"},{"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"},{"key":"e_1_3_2_1_7_1","first-page":"383","volume-title":"Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS)","author":"Baswana Surender","year":"2011"},{"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"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","first-page":"2492","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Behnezhad Soheil","year":"2020","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"},{"key":"e_1_3_2_1_11_1","first-page":"389","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC)","author":"Bernstein Aaron","year":"2016"},{"key":"e_1_3_2_1_12_1","first-page":"453","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bernstein Aaron","year":"2017"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","first-page":"167","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP)","author":"Bernstein Aaron","year":"2015","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_3_2_1_14_1","first-page":"692","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bernstein Aaron","year":"2016"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","first-page":"1899","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bernstein Aaron","year":"2019","DOI":"10.1137\/1.9781611975482.115"},{"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"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","first-page":"1872","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bhattacharya Sayan","year":"2019","DOI":"10.1137\/1.9781611975482.113"},{"key":"e_1_3_2_1_18_1","first-page":"398","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC)","author":"Bhattacharya Sayan","year":"2016"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","first-page":"86","volume-title":"Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO)","author":"Bhattacharya Sayan","year":"2017","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_1_20_1","first-page":"470","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bhattacharya Sayan","year":"2017"},{"key":"e_1_3_2_1_21_1","first-page":"1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bhattacharya Sayan","year":"2018"},{"key":"e_1_3_2_1_22_1","first-page":"219","volume":"261","author":"Bhattacharya Sayan","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"},{"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"},{"key":"e_1_3_2_1_25_1","first-page":"389","volume-title":"Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC)","author":"Chuzhoy Julia","year":"2019"},{"key":"e_1_3_2_1_26_1","volume-title":"On dynamic shortest paths with adaptive adversary. Unpublished manuscript","author":"Chuzhoy Julia","year":"2019"},{"key":"e_1_3_2_1_27_1","first-page":"960","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Cohen Ilan Reuven","year":"2018"},{"key":"e_1_3_2_1_28_1","first-page":"1","volume-title":"Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS)","author":"Cohen Ilan Reuven","year":"2019"},{"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"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","first-page":"1937","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Duan Ran","year":"2019","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"},{"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"},{"key":"e_1_3_2_1_33_1","first-page":"505","volume":"13","author":"Fleischer Lisa K","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"},{"key":"e_1_3_2_1_35_1","first-page":"26","volume-title":"Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS)","author":"Gamlath Buddhima","year":"2019"},{"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"},{"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"},{"key":"e_1_3_2_1_38_1","first-page":"129","volume-title":"Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC)","author":"Ghafari Mohsen","year":"2018"},{"key":"e_1_3_2_1_39_1","first-page":"468","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Goel Ashish","year":"2012"},{"key":"e_1_3_2_1_40_1","first-page":"537","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC)","author":"Gupta Anupam","year":"2017"},{"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"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","first-page":"2542","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Gutenberg Maximilian Probst","year":"2020","DOI":"10.1137\/1.9781611975994.155"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","first-page":"2522","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Gutenberg Maximilian Probst","year":"2020","DOI":"10.1137\/1.9781611975994.154"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","first-page":"21","volume-title":"Proceedings of the forty-seventh annual ACM symposium on Theory of computing","author":"Henzinger Monika","year":"2015","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"},{"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"},{"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"},{"key":"e_1_3_2_1_49_1","first-page":"99","volume-title":"Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science","author":"Ivkovic Zoran","year":"1993"},{"key":"e_1_3_2_1_50_1","first-page":"286","volume-title":"The Annals of Statistics","author":"Joag-Dev Kumar","year":"1983"},{"key":"e_1_3_2_1_51_1","first-page":"1131","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kapron Bruce M","year":"2013"},{"key":"e_1_3_2_1_52_1","first-page":"1183","volume":"10","author":"Khursheed Alam","journal-title":"Methods"},{"key":"e_1_3_2_1_53_1","first-page":"1272","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kopelowitz Tsvi","year":"2016"},{"key":"e_1_3_2_1_54_1","first-page":"355","volume-title":"Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO)","author":"Lee Euiwoong","year":"2017"},{"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"},{"key":"e_1_3_2_1_56_1","first-page":"17","volume-title":"Proceedings of the 21st Symposium on Foundations of Computer Science (FOCS)","author":"Micali Silvio","year":"1980"},{"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"},{"key":"e_1_3_2_1_58_1","first-page":"1122","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC)","author":"Nanongkai Danupon","year":"2017"},{"key":"e_1_3_2_1_59_1","volume-title":"Proceedings of the 58","author":"Nanongkai Danupon"},{"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"},{"key":"e_1_3_2_1_61_1","first-page":"457","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC)","author":"Onak Krzysztof","year":"2010"},{"key":"e_1_3_2_1_62_1","volume-title":"ACM Transactions on Algorithms (TALG), 15 ( 2 ): 18","author":"Paz Ami","year":"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"},{"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"},{"key":"e_1_3_2_1_65_1","first-page":"325","volume-title":"Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS)","author":"Solomon Shay","year":"2016"},{"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"},{"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"},{"key":"e_1_3_2_1_68_1","first-page":"343","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC)","author":"Thorup Mikkel","year":"2000"},{"key":"e_1_3_2_1_69_1","first-page":"456","volume-title":"Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS)","author":"van den Brand Jan","year":"2019"},{"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"},{"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"}],"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\/pdf\/10.1145\/3357713.3384258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:56:19Z","timestamp":1624917379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":71,"alternative-id":["10.1145\/3357713.3384258","10.1145\/3357713"],"URL":"http:\/\/dx.doi.org\/10.1145\/3357713.3384258","relation":{},"published":{"date-parts":[[2020,6,6]]}}}