{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:46:01Z","timestamp":1782971161857,"version":"3.54.5"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T00:00:00Z","timestamp":1467072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["724\/15"],"award-info":[{"award-number":["724\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israeli Academy of Science","award":["593\/11"],"award-info":[{"award-number":["593\/11"]}]},{"name":"US-Israel Binational Science Foundation","award":["2008390"],"award-info":[{"award-number":["2008390"]}]},{"name":"NSF","award":["CCF-0746673, CCF-1217338, CNS-1318294, and CCF-1514383"],"award-info":[{"award-number":["CCF-0746673, CCF-1217338, CNS-1318294, and CCF-1514383"]}]},{"DOI":"10.13039\/501100007277","name":"Center for Massive Data Algorithmics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007277","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Aarhus University"},{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"crossref","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>\n            Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the\n            <jats:italic>randomized<\/jats:italic>\n            complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following:\n          <\/jats:p>\n          <jats:p>\n            \u2014An MIS algorithm running in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            \u0394 + 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\u221alog log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) time, where \u0394 is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when log\n            <jats:italic>n<\/jats:italic>\n            \u226a \u0394 \u226a 2\u221alog\n            <jats:italic>n<\/jats:italic>\n            , and comes close to the \u03a9(log \u0394 \/ log log \u0394 lower bound of Kuhn, Moscibroda, and Wattenhofer.\n          <\/jats:p>\n          <jats:p>\n            \u2014A maximal matching algorithm running in\n            <jats:italic>O<\/jats:italic>\n            (log\u2009\u0394 + log\u2009\n            <jats:sup>4<\/jats:sup>\n            log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on \u0394 is\n            <jats:italic>nearly optimal<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            \u2014A (\u0394 + 1)-coloring algorithm requiring\n            <jats:italic>O<\/jats:italic>\n            (log \u0394 + 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\u221alog log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            time, improving on an\n            <jats:italic>O<\/jats:italic>\n            (log \u0394 + \u221alog\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm of Schneider and Wattenhofer.\n          <\/jats:p>\n          <jats:p>\n            \u2014A method for reducing symmetry-breaking problems in low arboricity\/degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an\n            <jats:italic>O<\/jats:italic>\n            (\u221alog\n            <jats:italic>n<\/jats:italic>\n            )-time maximal matching algorithm for graphs with arboricity up to 2\u221alog\n            <jats:italic>n<\/jats:italic>\n            and an\n            <jats:italic>O<\/jats:italic>\n            (log\u2009\n            <jats:sup>2\/3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-time MIS algorithm for graphs with arboricity up to 2\n            <jats:sup>\n              (log\n              <jats:italic>n<\/jats:italic>\n              )1\/3\n            <\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>\n            Each of our algorithms is based on a simple but powerful technique for reducing a\n            <jats:italic>randomized<\/jats:italic>\n            symmetry-breaking task to a corresponding\n            <jats:italic>deterministic<\/jats:italic>\n            one on a poly(log\u2009\n            <jats:italic>n<\/jats:italic>\n            )-size graph.\n          <\/jats:p>","DOI":"10.1145\/2903137","type":"journal-article","created":{"date-parts":[[2016,6,29]],"date-time":"2016-06-29T12:56:52Z","timestamp":1467205012000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":130,"title":["The Locality of Distributed Symmetry Breaking"],"prefix":"10.1145","volume":"63","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[{"name":"Ben-Gurion University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Elkin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"Schneider","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_3_1","unstructured":"A. Amir O. Kapah T. Kopelowitz M. Naor and E. Porat. 2014. The family holiday gathering problem or fair and periodic scheduling of independent sets. CoRR abs\/1408.2279 (2014).  A. Amir O. Kapah T. Kopelowitz M. Naor and E. Porat. 2014. The family holiday gathering problem or fair and periodic scheduling of independent sets. CoRR abs\/1408.2279 (2014)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 + &epsi;)-approximation for vertex cover in O(log&thinsp;\u0394&sol;&epsi;log&thinsp;log&thinsp;\u0394) rounds. CoRR abs\/1602.03713 (2016).  R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 + &epsi;)-approximation for vertex cover in O(log&thinsp;\u0394&sol;&epsi;log&thinsp;log&thinsp;\u0394) rounds. CoRR abs\/1602.03713 (2016).","DOI":"10.1145\/2933057.2933086"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers San Francisco CA.   L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers San Francisco CA.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611512"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611465"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge.   D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2%3C99::AID-RSA1%3E3.0.CO;2-M"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370","author":"Elkin M.","unstructured":"M. Elkin , S. Pettie , and H. H. Su . 2015. (2\u0394 &minus; 1)-edge coloring is much easier than maximal matching in the distributed setting . In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370 . M. Elkin, S. Pettie, and H. H. Su. 2015. (2\u0394 &minus; 1)-edge coloring is much easier than maximal matching in the distributed setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281111"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897533"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0174-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993812"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs","volume":"18","author":"Kothapalli K.","unstructured":"K. Kothapalli and S. V. Pemmaraju . 2012. Super-fast 3-ruling sets . In Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs , Vol. 18 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 136--147. K. Kothapalli and S. V. Pemmaraju. 2012. Super-fast 3-ruling sets. In Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, Vol. 18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 136--147."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS).","author":"Kothapalli K.","unstructured":"K. Kothapalli , C. Scheideler , M. Onus , and C. Schindelhauer . 2006. Distributed coloring in O&tilde;(&radic;log n) bit rounds . In Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS). K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. 2006. Distributed coloring in O&tilde;(&radic;log n) bit rounds. In Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_2_1_29_1","unstructured":"F. Kuhn T. Moscibroda and R. Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs\/1011.5470 (2010).  F. Kuhn T. Moscibroda and R. Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs\/1011.5470 (2010)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993813"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_36_1","first-page":"12","article-title":"Decomposition of finite graphs into forests","volume":"39","author":"St C.","year":"1964","unstructured":"C. St . J. A. Nash-Williams . 1964 . Decomposition of finite graphs into forests . J. London Math. Soc. 39 (1964), 12 . C. St. J. A. Nash-Williams. 1964. Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12.","journal-title":"J. London Math. Soc."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_2_1_39_1","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"Peleg D.","unstructured":"D. Peleg . 2000. Distributed Computing: A Locality-Sensitive Approach . SIAM , Philadelphia, PA . D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.018"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238","author":"Rubinfeld R.","unstructured":"R. Rubinfeld , G. Tamir , S. Vardi , and N. Xie . 2011. Fast local computation algorithms . In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238 . See also CoRR abs\/1104.1377. R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. 2011. Fast local computation algorithms. In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238. See also CoRR abs\/1104.1377."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"},{"key":"e_1_2_1_46_1","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\/2903137","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:15Z","timestamp":1750222575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2903137"],"URL":"https:\/\/doi.org\/10.1145\/2903137","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,28]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}