{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:26:50Z","timestamp":1756571210908,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T00:00:00Z","timestamp":1696982400000},"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":["J. ACM"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            The study of approximate matching in the\n            <jats:italic>Massively Parallel Computations<\/jats:italic>\n            (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of\n            <jats:italic>maximal matching<\/jats:italic>\n            which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03a9 (1)<\/jats:sup>\n            per machine.\n          <\/jats:p>\n          <jats:p>\n            In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [\n            <jats:xref ref-type=\"bibr\">15<\/jats:xref>\n            ]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an\n            <jats:italic>O<\/jats:italic>\n            (log log \u0394) round algorithm for maximal matching with\n            <jats:italic>O(n)<\/jats:italic>\n            space (or even\n            <jats:italic>mildly sublinear<\/jats:italic>\n            in\n            <jats:italic>n<\/jats:italic>\n            using standard techniques).\n          <\/jats:p>\n          <jats:p>\n            As an immediate corollary, we get a 2 approximate\n            <jats:italic>minimum vertex cover<\/jats:italic>\n            in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved\n            <jats:italic>O<\/jats:italic>\n            (log log \u0394) round algorithm for 1 + \u03b5 approximate matching. All these results can also be implemented in the\n            <jats:italic>congested clique<\/jats:italic>\n            model in the same number of rounds.\n          <\/jats:p>","DOI":"10.1145\/3617360","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T11:56:37Z","timestamp":1692964597000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Exponentially Faster Massively Parallel Maximal Matching"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0104-633X","authenticated-orcid":false,"given":"Soheil","family":"Behnezhad","sequence":"first","affiliation":[{"name":"Khoury College of Computer Sciences, Northeastern University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4842-0533","authenticated-orcid":false,"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3021-3555","authenticated-orcid":false,"given":"David G.","family":"Harris","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,10,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_3_5_2","unstructured":"Sepehr Assadi. 2017. Simple round compression for parallel vertex cover. arXiv:1709.04599. Retrieved from https:\/\/arxiv.org\/abs\/1709.04599"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.98"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087581"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.18"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_3_3_11_2","first-page":"6867","volume-title":"Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Bateni MohammadHossein","year":"2017","unstructured":"MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab S. Mirrokni. 2017. Affinity clustering: Hierarchical clustering at scale. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS\u201917). 6867\u20136877. Retrieved from http:\/\/papers.nips.cc\/paper\/7262-affinity-clustering-hierarchical-clustering-at-scale"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087601"},{"key":"e_1_3_3_14_2","unstructured":"Soheil Behnezhad Mahsa Derakhshan and MohammadTaghi Hajiaghayi. 2018. Brief announcement: Semi-MapReduce meets congested clique. arXiv:1802.10297. Retrieved from https:\/\/arxiv.org\/abs\/1802.10297"},{"key":"e_1_3_3_15_2","unstructured":"Soheil Behnezhad Mahsa Derakhshan MohammadTaghi Hajiaghayi and Richard M. Karp. 2018. Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. arXiv:1807.06701. Retrieved from https:\/\/arxiv.org\/abs\/1807.06701"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520039"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087830"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/080714403"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_3_34_2","unstructured":"Krzysztof Onak. 2018. Round compression for parallel graph algorithms in strongly sublinear space. arXiv:1807.08745. Retrieved from https:\/\/arxiv.org\/abs\/1807.08745"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349952"},{"key":"e_1_3_3_36_2","volume-title":"Hadoop: The Definitive Guide (2nd. ed.)","author":"White Tom","year":"2011","unstructured":"Tom White. 2011. Hadoop: The Definitive Guide (2nd. ed.). O\u2019Reilly. Retrieved from https:\/\/www.oreilly.com\/library\/view\/hadoop-the-definitive\/9781449398644\/"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud\u201910)","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster computing with working sets. In Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud\u201910). Retrieved from https:\/\/www.usenix.org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617360","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617360","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:45:53Z","timestamp":1750178753000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,11]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3617360"],"URL":"https:\/\/doi.org\/10.1145\/3617360","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,10,11]]},"assertion":[{"value":"2022-12-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}