{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T14:59:03Z","timestamp":1784905143135,"version":"3.55.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,10,31]],"date-time":"2021-10-31T00:00:00Z","timestamp":1635638400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["285721 and 314888"],"award-info":[{"award-number":["285721 and 314888"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ESTATE","award":["ANR-16-CE25-0009-03"],"award-info":[{"award-number":["ANR-16-CE25-0009-03"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            There are distributed graph algorithms for finding maximal matchings and maximal independent sets in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0394<\/jats:italic>\n            + log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) communication rounds; here,\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes and\n            <jats:italic>\u0394<\/jats:italic>\n            is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on\n            <jats:italic>n<\/jats:italic>\n            is optimal: These problems cannot be solved in\n            <jats:italic>o<\/jats:italic>\n            (log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) rounds even if\n            <jats:italic>\u0394<\/jats:italic>\n            = 2. However, the dependency on\n            <jats:italic>\u0394<\/jats:italic>\n            is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds.\n          <\/jats:p>\n          <jats:p>\n            We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1-1\/\n            <jats:italic>n<\/jats:italic>\n            requires \u03a9 (min {\n            <jats:italic>\u0394<\/jats:italic>\n            , log log\n            <jats:italic>n<\/jats:italic>\n            \/ log log log\n            <jats:italic>n<\/jats:italic>\n            }) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires \u03a9 (min {\n            <jats:italic>\u0394<\/jats:italic>\n            , log\n            <jats:italic>n<\/jats:italic>\n            \/ log log\n            <jats:italic>n<\/jats:italic>\n            }) rounds; this is an improvement over prior lower bounds also as a function of\u00a0\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3461458","type":"journal-article","created":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T21:55:23Z","timestamp":1638827723000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Lower Bounds for Maximal Matchings and Maximal Independent Sets"],"prefix":"10.1145","volume":"68","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Aalto University, Finland and University of Freiburg, Freiburg im Breisgau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[{"name":"Aalto University, Aalto, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Aalto University, Finland and University of Freiburg, Freiburg im Breisgau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mika\u00ebl","family":"Rabie","sequence":"additional","affiliation":[{"name":"Aalto University, Finland and Universit\u00e9 de Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[{"name":"Aalto University, Aalto, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,6]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810533"},{"key":"e_1_3_1_4_2","unstructured":"Alkida Balliu Sebastian Brandt Yuval Efron Juho Hirvonen Yannic Maus Dennis Olivetti and Jukka Suomela. 2019. Classification of distributed binary labeling problems. In Proceedings of the 34th International Symposium on Distributed Computing 2020 October 12-16 2020 . 17:1\u201317:17. DOI:10.4230\/LIPIcs.DISC.2020.17"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00042"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331605"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2979675"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331611"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Sebastian Brandt and Dennis Olivetti. 2020. Truly Tight-in- Bounds for Bipartite Maximal Matching and Variants. In ACM Symposium on Principles of Distributed Computing 2020 Virtual Event Italy August 3-7 2020 . 69\u201378. DOI:10.1145\/3382734.3405745","DOI":"10.1145\/3382734.3405745"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.168"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.72"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.21"},{"key":"e_1_3_1_19_2","first-page":"17:1\u201317:15","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917)","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer. 2017. Improved deterministic distributed matching via rounding. In Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917). 17:1\u201317:15. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.17"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.73"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20293"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_1_23_2","unstructured":"Mohsen Ghaffari. 2017. LOCAL Algorithms: The chasm between deterministic and randomized. In Proceedings of the 6th Workshop on Advances in Distributed Graph Algorithms (ADGA\u201917) . http:\/\/adga.hiit.fi\/2017\/ghaffari.pdf."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0245-8"},{"key":"e_1_3_1_25_2","first-page":"219","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998)","author":"Hanckowiak Michal","year":"1998","unstructured":"Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. 1998. On the distributed complexity of computing maximal matchings. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998). ACM\/SIAM, 219\u2013225."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332464"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109666"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","unstructured":"Dennis Olivetti. 2020. Round Eliminator: A Tool for Automatic Speedup Simulation. https:\/\/github.com\/olidennis\/round-eliminator.","DOI":"10.1145\/3382734.3405694"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_1_43_2","unstructured":"Jukka Suomela. 2014. Lower bounds for local algorithms. In Proceedings of the 3rd Workshop on Advances in Distributed Graph Algorithms (ADGA\u201914) . http:\/\/adga2014.hiit.fi\/jukka.pdf."},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167156"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461458","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3461458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:35Z","timestamp":1750195715000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,31]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3461458"],"URL":"https:\/\/doi.org\/10.1145\/3461458","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,31]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}