{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T12:33:50Z","timestamp":1786624430165,"version":"build-2736575974"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T00:00:00Z","timestamp":1786579200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,8,31]]},"abstract":"<jats:p>\n                    We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a \u0394-coloring on \u0394-regular trees requires \u03a9 (log\n                    <jats:sub>\u0394<\/jats:sub>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds and any randomized such algorithm requires \u03a9 (log\n                    <jats:sub>\u0394<\/jats:sub>\n                    log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds. We prove this by showing that a natural relaxation of the \u0394-coloring problem is a fixed point in the round elimination framework.\n                  <\/jats:p>\n                  <jats:p>\n                    As a first application, we show that our \u0394-coloring lower bound proof directly extends to arbdefective colorings. An arbdefective\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -coloring of a graph\n                    <jats:italic toggle=\"yes\">G=(V,E)<\/jats:italic>\n                    is given by a\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -coloring of\n                    <jats:italic toggle=\"yes\">V<\/jats:italic>\n                    and an orientation of\n                    <jats:italic toggle=\"yes\">E<\/jats:italic>\n                    , where the arbdefect of a color\n                    <jats:italic toggle=\"yes\">i<\/jats:italic>\n                    is the maximum number of monochromatic outgoing edges of any node of color\n                    <jats:italic toggle=\"yes\">i<\/jats:italic>\n                    . We exactly characterize which variants of the arbdefective coloring problem can be solved in\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    (\u0394) + log\n                    <jats:sup>*<\/jats:sup>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds, for some function\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    , and which of them instead require \u03a9 (log\n                    <jats:sub>\u0394<\/jats:sub>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds for deterministic algorithms and \u03a9 (log\n                    <jats:sub>\u0394<\/jats:sub>\n                    log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds for randomized ones.\n                  <\/jats:p>\n                  <jats:p>\n                    As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of \u0394 for problems that, in some sense, are\n                    <jats:italic toggle=\"yes\">much easier<\/jats:italic>\n                    than \u0394-coloring, as they can be solved in\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:sup>*<\/jats:sup>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) deterministic rounds in bounded-degree graphs. More specifically, we prove lower bounds as a function of \u0394 for a large class of distributed symmetry breaking problems, which can all be solved by a simple sequential greedy algorithm. For example, we obtain novel results for the fundamental problem of computing a (2,\u03b2)-ruling set, i.e., for computing an independent set\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    \u2286\n                    <jats:italic toggle=\"yes\">V<\/jats:italic>\n                    such that every node\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    \u2208\n                    <jats:italic toggle=\"yes\">V<\/jats:italic>\n                    is within distance \u2264 \u03b2 of some node in\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    . We in particular show that \u03a9 (\u03b2 \u0394\n                    <jats:sup>1\/\u03b2<\/jats:sup>\n                    ) rounds are needed even if initially an\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\u0394)-coloring of the graph is given. With an initial\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\u0394)-coloring, this lower bound is tight and without, it still nearly matches the existing\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\u03b2 \u0394\n                    <jats:sup>2\/(\u03b2 +1)<\/jats:sup>\n                    +log\n                    <jats:sup>*<\/jats:sup>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) upper bound. The new (2,\u03b2)-ruling set lower bound is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS \u201920]. As a special case of the lower bound, we also obtain a tight linear-in-\u0394 lower bound for computing a maximal independent set (MIS) in trees. While such an MIS lower bound was known for general graphs, the best previous MIS lower bounds for trees was \u03a9 (log \u0394). Our lower bound even applies to a much more general family of problems that allows for almost arbitrary combinations of natural constraints from coloring problems, orientation problems, and independent set problems, and provides a single unified proof for known and new lower bound results for these types of problems.\n                  <\/jats:p>\n                  <jats:p>\n                    All of our lower bounds as a function of \u0394 also imply substantial lower bounds as a function of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    . For instance, we obtain that the maximal independent set problem, on trees, requires \u03a9 (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    \/ log log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds for deterministic algorithms, which is tight.\n                  <\/jats:p>","DOI":"10.1145\/3819817","type":"journal-article","created":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T21:08:17Z","timestamp":1781644097000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Distributed \u0394-Coloring Plays Hide-and-Seek"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5293-8365","authenticated-orcid":false,"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute","place":["L'Aquila, Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5393-6636","authenticated-orcid":false,"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security","place":["Saarbr\u00fccken, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5343-5953","authenticated-orcid":false,"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Freiburg","place":["Freiburg, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6600-6443","authenticated-orcid":false,"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute","place":["L'Aquila, Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,13]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_3_3_2","first-page":"364","volume-title":"Proceedings of the 30th Symp. on Foundations of Computer Science","author":"Awerbuch Baruch","year":"1989","unstructured":"Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network decomposition and locality in distributed computation. In Proceedings of the 30th Symp. on Foundations of Computer Science. 364\u2013369. DOI:10.1109\/SFCS.1989.63504"},{"key":"e_1_3_3_4_2","volume-title":"Proceedings of the 34th Symp. on Distributed Computing","author":"Balliu Alkida","year":"2020","unstructured":"Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. 2020. Classification of distributed binary labeling problems. In Proceedings of the 34th Symp. on Distributed Computing. DOI:10.4230\/LIPIcs.DISC.2020.17"},{"key":"e_1_3_3_5_2","first-page":"481","volume-title":"Proceedings of the 60th IEEE Symp. on Foundations of Computer Science","author":"Balliu Alkida","year":"2019","unstructured":"Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2019. Lower bounds for maximal matchings and maximal independent sets. In Proceedings of the 60th IEEE Symp. on Foundations of Computer Science. 481\u2013497. DOI:10.1109\/FOCS.2019.00037"},{"key":"e_1_3_3_6_2","volume-title":"Proceedings of the 40th ACM Symposium on Principles of Distributed Computing","author":"Balliu Alkida","year":"2021","unstructured":"Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2021. Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing. DOI:10.1145\/3465084.3467901"},{"key":"e_1_3_3_7_2","first-page":"365","volume-title":"Proceedings of the 61st IEEE Symp. on Foundations of Computer Science","author":"Balliu Alkida","year":"2020","unstructured":"Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. 2020. Distributed lower bounds for ruling sets. In Proceedings of the 61st IEEE Symp. on Foundations of Computer Science. 365\u2013376. DOI:10.1109\/FOCS46700.2020.00042"},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1145\/3293611.3331605","volume-title":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","author":"Balliu Alkida","year":"2019","unstructured":"Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. 2019. Hardness of minimal symmetry breaking in distributed computing. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 369\u2013378. DOI:10.1145\/3293611.3331605"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2979675"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00520ED1V01Y201307DCT011"},{"key":"e_1_3_3_13_2","first-page":"437","volume-title":"Proceedings of the 37th ACM Symp. on Principles of Distributed Computing","author":"Barenboim Leonid","year":"2018","unstructured":"Leonid Barenboim, Michael Elkin, and Uri Goldenberg. 2018. Locally-iterative distributed \\((\\Delta +1)\\) -coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In Proceedings of the 37th ACM Symp. on Principles of Distributed Computing. 437\u2013446. DOI:10.1145\/3212734.3212769"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/2611462.2611512","volume-title":"Proceedings of the 2014 Symposium on Principles of Distributed Computing","author":"Bisht Tushar","year":"2014","unstructured":"Tushar Bisht, Kishore Kothapalli, and Sriram V. Pemmaraju. 2014. Brief announcement: Super-fast t-ruling sets. In Proceedings of the 2014 Symposium on Principles of Distributed Computing. 379\u2013381. DOI:10.1145\/2611462.2611512"},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/3293611.3331611","volume-title":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","author":"Brandt Sebastian","year":"2019","unstructured":"Sebastian Brandt. 2019. An automatic speedup theorem for distributed problems. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 379\u2013388. DOI:10.1145\/3293611.3331611"},{"key":"e_1_3_3_18_2","first-page":"479","volume-title":"Proceedings of the 48th ACM Symposium on Theory of Computing","author":"Brandt Sebastian","year":"2016","unstructured":"Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi\u00e4inen, Joel Rybicki, Jukka Suomela, and Jara Uitto. 2016. A lower bound for the distributed Lov\u00e1sz local lemma. In Proceedings of the 48th ACM Symposium on Theory of Computing. ACM, 479\u2013488. DOI:10.1145\/2897518.2897570"},{"key":"e_1_3_3_19_2","first-page":"69","volume-title":"Proceedings fo the 39th ACM Symp. on Principles of Distributed Computing","author":"Brandt Sebastian","year":"2020","unstructured":"Sebastian Brandt and Dennis Olivetti. 2020. Truly tight-in- \\(\\Delta\\) bounds for bipartite maximal matching and variants. In Proceedings fo the 39th ACM Symp. on Principles of Distributed Computing. 69\u201378. DOI:10.1145\/3382734.3405745"},{"key":"e_1_3_3_20_2","first-page":"194","volume-title":"Mathematical Proceedings of the Cambridge Philosophical Society","author":"Brooks Rowland Leonard","year":"1941","unstructured":"Rowland Leonard Brooks. 1941. On colouring the nodes of a network. In Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press, 194\u2013197. DOI:10.1017\/S030500410002168X"},{"key":"e_1_3_3_21_2","first-page":"11:1\u201311:16","volume-title":"ProcProceedings of the 31st Symp. on Distributed Computing","author":"Censor-Hillel K.","year":"2017","unstructured":"K. Censor-Hillel, M. Parter, and G. Schwartzman. 2017. Derandomizing local distributed algorithms under bandwidth restrictions. In ProcProceedings of the 31st Symp. on Distributed Computing. 11:1\u201311:16. DOI:10.4230\/LIPIcs.DISC.2017.11"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249527"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157957"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"4409","DOI":"10.1137\/1.9781611977554.ch168","volume-title":"Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms","author":"Faour Salwa","year":"2023","unstructured":"Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and V\u00e1clav Rozhon. 2023. Local distributed rounding: Generalized to MIS, matching, set cover, and beyond. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms. SIAM, 4409\u20134447. DOI:10.1137\/1.9781611977554.ch168"},{"key":"e_1_3_3_27_2","series-title":"LIPIcs","first-page":"18:1\u201318:16","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing.","volume":"91","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer and Mohsen Ghaffari. 2017. Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma, and the complexity hierarchy. In Proceedings of the 31st International Symposium on Distributed Computing.Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, Vol. 91, 18:1\u201318:16. DOI:10.4230\/LIPIcs.DISC.2017.18"},{"key":"e_1_3_3_28_2","first-page":"625","volume-title":"Proceedings of the 57th IEEE Symp. on Foundations of Computer Science","author":"Fraigniaud Pierre","year":"2016","unstructured":"Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2016. Local conflict coloring. In Proceedings of the 57th IEEE Symp. on Foundations of Computer Science. 625\u2013634. DOI:10.1109\/FOCS.2016.73"},{"key":"e_1_3_3_29_2","first-page":"128:1\u2013128:18","volume-title":"Proceedings of the 47th Int. Coll. on Automata, Languages, and Programming","author":"Fraigniaud Pierre","year":"2020","unstructured":"Pierre Fraigniaud and Ami Paz. 2020. The topology of local computing in networks. In Proceedings of the 47th Int. Coll. on Automata, Languages, and Programming. 128:1\u2013128:18. DOI:10.4230\/LIPIcs.ICALP.2020.128"},{"key":"e_1_3_3_30_2","first-page":"53","volume-title":"Proceedings of the 2007 ACM Symposium on Principles of Distributed Computing","author":"Gfeller Beat","year":"2007","unstructured":"Beat Gfeller and Elias Vicari. 2007. A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In Proceedings of the 2007 ACM Symposium on Principles of Distributed Computing. 53\u201360. DOI:10.1145\/1281100.1281111"},{"key":"e_1_3_3_31_2","first-page":"270","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ghaffari Mohsen","year":"2016","unstructured":"Mohsen Ghaffari. 2016. An improved distributed algorithm for maximal independent set. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. 270\u2013277. DOI:10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_3_32_2","first-page":"805","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari. 2019. Distributed maximal independent set using small messages. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. 805\u2013820. DOI:10.1137\/1.9781611975482.50"},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1145\/3564246.3585243","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing.","author":"Ghaffari Mohsen","year":"2023","unstructured":"Mohsen Ghaffari and Christoph Grunau. 2023. Faster deterministic distributed MIS and approximate matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing.Association for Computing Machinery, New York, NY, USA, 1777\u20131790. DOI:10.1145\/3564246.3585243"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"2904","DOI":"10.1137\/1.9781611976465.173","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari, Christoph Grunau, and V\u00e1clav Rozhon. 2021. Improved deterministic network decomposition. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms. D\u00e1niel Marx (Ed.), SIAM, 2904\u20132923. DOI:10.1137\/1.9781611976465.173"},{"key":"e_1_3_3_35_2","first-page":"662","volume-title":"Proceedings of the 59th Symp. on Foundations of Computer Science","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. 2018. On derandomizing local distributed algorithms. In Proceedings of the 59th Symp. on Foundations of Computer Science. 662\u2013673. DOI:10.1109\/FOCS.2018.00069"},{"key":"e_1_3_3_36_2","first-page":"427","volume-title":"Proceedings of the 37th ACM Symp. on Principles of Distributed Computing","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. 2018. Improved distributed \\(\\Delta\\) -coloring. In Proceedings of the 37th ACM Symp. on Principles of Distributed Computing. 427\u2013436. DOI:10.1145\/3212734.3212764"},{"key":"e_1_3_3_37_2","volume-title":"Proceedings of the 62nd IEEE Symp. on Foundations of Computing","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari and Fabian Kuhn. 2021. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proceedings of the 62nd IEEE Symp. on Foundations of Computing."},{"key":"e_1_3_3_38_2","first-page":"18:1\u201318:16","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari and Julian Portmann. 2019. Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond. In Proceedings of the 33rd International Symposium on Distributed Computing. 18:1\u201318:16. DOI:10.4230\/LIPIcs.DISC.2019.18"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_3_3_40_2","first-page":"489","volume-title":"Proceedings of the 48th Symp. on Theory of Computing","author":"Henzinger Monika","year":"2016","unstructured":"Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the 48th Symp. on Theory of Computing. 489\u2013498. DOI:10.1145\/2897518.2897638"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4226"},{"key":"e_1_3_3_42_2","first-page":"136","volume-title":"Proceedings of the Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Kothapalli Kishore","year":"2012","unstructured":"Kishore Kothapalli and Sriram V. Pemmaraju. 2012. Super-fast 3-ruling sets. In Proceedings of the Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 136\u2013147. DOI:10.4230\/LIPIcs.FSTTCS.2012.136"},{"key":"e_1_3_3_43_2","volume-title":"Proceedings of the 21st ACM Symp. on Parallelism in Algorithms and Architectures","author":"Kuhn Fabian","year":"2009","unstructured":"Fabian Kuhn. 2009. Local weak coloring algorithms and implications on deterministic symmetry breaking. In Proceedings of the 21st ACM Symp. on Parallelism in Algorithms and Architectures."},{"key":"e_1_3_3_44_2","first-page":"1244","volume-title":"Proceedings of the 32st ACM-SIAM Symp. on Discrete Algorithms","author":"Kuhn Fabian","year":"2020","unstructured":"Fabian Kuhn. 2020. Faster deterministic distributed coloring through recursive list coloring. In Proceedings of the 32st ACM-SIAM Symp. on Discrete Algorithms. 1244\u20131259. DOI:10.1137\/1.9781611975994.76"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01325-7_19"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_3_47_2","first-page":"41","volume-title":"Proceedings of the 2011 Annual ACM Symposium on Principles of Distributed","author":"Lenzen Christoph","year":"2011","unstructured":"Christoph Lenzen and Roger Wattenhofer. 2011. MIS on trees. In Proceedings of the 2011 Annual ACM Symposium on Principles of Distributed. 41\u201348. DOI:10.1145\/1993806.1993813"},{"key":"e_1_3_3_48_2","first-page":"331","volume-title":"Proceedings of the 28th Symp. on Foundations of Computer Science","author":"Linial Nathan","year":"1987","unstructured":"Nathan Linial. 1987. Distributive graph algorithms \u2013 Global solutions from local data. In Proceedings of the 28th Symp. on Foundations of Computer Science. IEEE, 331\u2013335. DOI:10.1109\/SFCS.1987.20"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_3_51_2","volume-title":"Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures","author":"Maus Yannic","year":"2021","unstructured":"Yannic Maus. 2021. Distributed graph coloring made easy. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. DOI:10.1145\/3409964.3461804"},{"key":"e_1_3_3_52_2","series-title":"LIPIcs","first-page":"16:1\u201316:18","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing","volume":"179","author":"Maus Yannic","year":"2020","unstructured":"Yannic Maus and Tigran Tonoyan. 2020. Local conflict coloring revisited: Linial for lists. In Proceedings of the 34th International Symposium on Distributed Computing. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, 179 (2020), 16:1\u201316:18. DOI:10.4230\/LIPIcs.DISC.2020.16"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_3_54_2","doi-asserted-by":"crossref","unstructured":"Dennis Olivetti. 2019. Round Eliminator: A tool for automatic speedup simulation. Retrieved from https:\/\/github.com\/olidennis\/round-eliminator","DOI":"10.1145\/3382734.3405694"},{"key":"e_1_3_3_55_2","first-page":"38:1\u201338:16","volume-title":"Proceedings of 31st International Symposium on Distributed Computing","author":"Pai Shreyas","year":"2017","unstructured":"Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. 2017. Symmetry breaking in the CONGEST model: Time- and message-efficient algorithms for ruling sets. In Proceedings of 31st International Symposium on Distributed Computing. 38:1\u201338:16. DOI:10.4230\/LIPIcs.DISC.2017.38"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200759"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_3_59_2","volume-title":"Proceedings of the 52nd Annual ACM Symposium on Theory of Computing","author":"Rozho\u0148 V\u00e1clav","year":"2020","unstructured":"V\u00e1clav Rozho\u0148 and Mohsen Ghaffari. 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing. DOI:10.1145\/3357713.3384298"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.004"},{"key":"e_1_3_3_61_2","first-page":"257","volume-title":"Proceedings of the 2010 Annual ACM Symposium on Principles of Distributed Computing","author":"Schneider Johannes","year":"2010","unstructured":"Johannes Schneider and Roger Wattenhofer. 2010. A new technique for distributed symmetry breaking. In Proceedings of the 2010 Annual ACM Symposium on Principles of Distributed Computing. 257\u2013266. DOI:10.1145\/1835698.1835760"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3819817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T11:59:01Z","timestamp":1786622341000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3819817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,13]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,8,31]]}},"alternative-id":["10.1145\/3819817"],"URL":"https:\/\/doi.org\/10.1145\/3819817","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,13]]},"assertion":[{"value":"2024-12-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}