{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T03:48:30Z","timestamp":1777175310972,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188764","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"471-484","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Round compression for parallel matching algorithms"],"prefix":"10.1145","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"\u0141\u0105cki","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"M\u0105dry","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Slobodan","family":"Mitrovi\u0107","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Onak","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_2_3_1","unstructured":"Alexandr Andoni Aleksandar Nikolov Krzysztof Onak and Grigory Yaroslavtsev. 2014. Alexandr Andoni Aleksandar Nikolov Krzysztof Onak and Grigory Yaroslavtsev. 2014."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_2_5_1","volume-title":"Simple Round Compression for Parallel Vertex Cover. CoRR abs\/1709.04599 (September","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi . 2017. Simple Round Compression for Parallel Vertex Cover. CoRR abs\/1709.04599 (September 2017 ). https:\/\/arxiv.org\/abs\/1709.04599 Sepehr Assadi. 2017. Simple Round Compression for Parallel Vertex Cover. CoRR abs\/1709.04599 (September 2017). https:\/\/arxiv.org\/abs\/1709.04599"},{"key":"e_1_3_2_2_6_1","volume-title":"Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. CoRR abs\/1711","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab S. Mirrokni , and Cliff Stein . 2017 . Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. CoRR abs\/1711 .03076 (2017). arXiv: 1711.03076 http: \/\/arxiv.org\/abs\/1711.03076 Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. 2017. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. CoRR abs\/1711.03076 (2017). arXiv: 1711.03076 http: \/\/arxiv.org\/abs\/1711.03076"},{"key":"e_1_3_2_2_7_1","unstructured":"Sepehr Assadi and Sanjeev Khanna. 2017. Sepehr Assadi and Sanjeev Khanna. 2017."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087581"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28405"},{"key":"e_1_3_2_2_10_1","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2013. Paul Beame Paraschos Koutris and Dan Suciu. 2013."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_2_12_1","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2014. Paul Beame Paraschos Koutris and Dan Suciu. 2014."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_3_2_2_14_1","unstructured":"212\u2013223. 212\u2013223."},{"key":"e_1_3_2_2_15_1","unstructured":"Aaron Bernstein and Cliff Stein. 2015. Aaron Bernstein and Cliff Stein. 2015."},{"key":"e_1_3_2_2_16_1","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP","author":"Bipartite Graphs Fully Dynamic","year":"2015","unstructured":"Fully Dynamic Matching in Bipartite Graphs . In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015 , Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I. 167\u2013179. 3- 662- 47672- 7_14 Fully Dynamic Matching in Bipartite Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I. 167\u2013179. 3- 662- 47672- 7_14"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_2_18_1","unstructured":"692\u2013711. 692\u2013711."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_2_20_1","volume-title":"Italiano","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Giuseppe F . Italiano . 2015 . Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. 2015."},{"key":"e_1_3_2_2_21_1","volume-title":"Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Deterministic","year":"2015","unstructured":"Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , San Diego, CA, USA, January 4\u20136 , 2015 . 785\u2013804. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015. 785\u2013804."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_2_23_1","volume-title":"Proceedings of the 28th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017","author":"Bhattacharya Sayan","year":"2017","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Danupon Nanongkai . 2017 . Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O (log 3 n) Worst Case Update Time . In Proceedings of the 28th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16\u201319. 470\u2013489. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. 2017. Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O (log 3 n) Worst Case Update Time. In Proceedings of the 28th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319. 470\u2013489."},{"key":"e_1_3_2_2_24_1","volume-title":"Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation","volume":"6","author":"Dean Jeffrey","year":"2004","unstructured":"Jeffrey Dean and Sanjay Ghemawat . 2004 . MapReduce: Simplified Data Processing on Large Clusters . In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation , Volume 6 (OSDI\u201904). USENIX Association, Berkeley, CA, USA, 10\u201310. http:\/\/dl.acm.org\/citation.cfm?id=1251254.1251264 Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified Data Processing on Large Clusters. In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation, Volume 6 (OSDI\u201904). USENIX Association, Berkeley, CA, USA, 10\u201310. http:\/\/dl.acm.org\/citation.cfm?id=1251254.1251264"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_2_26_1","volume-title":"Canadian Journal of Mathematics","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds . 1965. Paths, Trees and Flowers . Canadian Journal of Mathematics ( 1965 ), 449\u2013467. Jack Edmonds. 1965. Paths, Trees and Flowers. Canadian Journal of Mathematics (1965), 449\u2013467."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824786"},{"key":"e_1_3_2_2_28_1","unstructured":"1824786 1824786"},{"key":"e_1_3_2_2_29_1","volume-title":"Faster, Better. CoRR abs\/1703.00900","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer and Mohsen Ghaffari . 2017. Deterministic Distributed Matching: Simpler , Faster, Better. CoRR abs\/1703.00900 ( 2017 ). http:\/\/arxiv.org\/abs\/1703. Manuela Fischer and Mohsen Ghaffari. 2017. Deterministic Distributed Matching: Simpler, Faster, Better. CoRR abs\/1703.00900 (2017). http:\/\/arxiv.org\/abs\/1703."},{"key":"e_1_3_2_2_30_1","unstructured":"00900 00900"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301360"},{"key":"e_1_3_2_2_34_1","unstructured":"Zengfeng Huang Bo\u017eidar Radunovi\u0107 Milan Vojnovi\u0107 and Qin Zhang. 2015. Zengfeng Huang Bo\u017eidar Radunovi\u0107 Milan Vojnovi\u0107 and Qin Zhang. 2015."},{"key":"e_1_3_2_2_35_1","volume-title":"Complexity of Approximate Matching in Distributed Graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4\u20137","author":"Communication","year":"2015","unstructured":"Communication Complexity of Approximate Matching in Distributed Graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4\u20137 , 2015 , Garching, Germany. 460\u2013473. Communication Complexity of Approximate Matching in Distributed Graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4\u20137, 2015, Garching, Germany. 460\u2013473."},{"key":"e_1_3_2_2_36_1","unstructured":"Michael Isard Mihai Budiu Yuan Yu Andrew Birrell and Dennis Fetterly. 2007. Michael Isard Mihai Budiu Yuan Yu Andrew Birrell and Dennis Fetterly. 2007."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_3_2_2_38_1","unstructured":"Amos Israeli and Alon Itai. 1986. Amos Israeli and Alon Itai. 1986."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Amos Israeli and Yossi Shiloach. 1986. Amos Israeli and Yossi Shiloach. 1986.","DOI":"10.1242\/jcs.1986.Supplement_5.4"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90141-9"},{"key":"e_1_3_2_2_42_1","unstructured":"Michael Kapralov Sanjeev Khanna and Madhu Sudan. 2014. Michael Kapralov Sanjeev Khanna and Madhu Sudan. 2014."},{"key":"e_1_3_2_2_43_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014","author":"Approximating","year":"2014","unstructured":"Approximating matching size from random streams . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 , Portland, Oregon, USA, January 5\u20137 , 2014 . 734\u2013751. Approximating matching size from random streams. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014. 734\u2013751."},{"key":"e_1_3_2_2_44_1","unstructured":"Howard J. Karloff Siddharth Suri and Sergei Vassilvitskii. 2010. Howard J. Karloff Siddharth Suri and Sergei Vassilvitskii. 2010."},{"key":"e_1_3_2_2_45_1","volume-title":"Model of Computation for MapReduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"A","year":"2010","unstructured":"A Model of Computation for MapReduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 , Austin, Texas, USA, January 17\u201319 , 2010 . 938\u2013948. A Model of Computation for MapReduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17\u201319, 2010. 938\u2013948."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109666"},{"key":"e_1_3_2_2_47_1","unstructured":"1109666 1109666"},{"key":"e_1_3_2_2_48_1","unstructured":"Silvio Lattanzi Benjamin Moseley Siddharth Suri and Sergei Vassilvitskii. 2011. Silvio Lattanzi Benjamin Moseley Siddharth Suri and Sergei Vassilvitskii. 2011."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_2_52_1","unstructured":"0215074 0215074"},{"key":"e_1_3_2_2_53_1","unstructured":"Andrew McGregor. 2005. Andrew McGregor. 2005."},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935799"},{"key":"e_1_3_2_2_58_1","unstructured":"Tom White. 2012. Tom White. 2012."},{"key":"e_1_3_2_2_59_1","volume-title":"The Definitive Guide. O\u2019Reilly Media","author":"Hadoop","unstructured":"Hadoop : The Definitive Guide. O\u2019Reilly Media , Inc . Hadoop: The Definitive Guide. O\u2019Reilly Media, Inc."},{"key":"e_1_3_2_2_60_1","unstructured":"Matei Zaharia Mosharaf Chowdhury Michael J. Franklin Scott Shenker and Ion Stoica. 2010. Matei Zaharia Mosharaf Chowdhury Michael J. Franklin Scott Shenker and Ion Stoica. 2010."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188764","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T07:03:39Z","timestamp":1751699019000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":60,"alternative-id":["10.1145\/3188745.3188764","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188764","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}