{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:12:38Z","timestamp":1757617958227,"version":"3.44.0"},"reference-count":64,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,25]],"date-time":"2025-05-25T00:00:00Z","timestamp":1748131200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,25]],"date-time":"2025-05-25T00:00:00Z","timestamp":1748131200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002666","name":"Aalto University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002666","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph <jats:italic>G<\/jats:italic>. Typically, the problem instance in CONGEST is identical to the communication network <jats:italic>G<\/jats:italic>, that is, we perform the symmetry breaking in <jats:italic>G<\/jats:italic>. In this work, we consider a setting where the problem instance corresponds to a power graph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$G^k$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, where each node of the communication network <jats:italic>G<\/jats:italic> is connected to all of its <jats:italic>k<\/jats:italic>-hop neighbors. A <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\beta $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b2<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-ruling set is a set of non-adjacent nodes such that each node in <jats:italic>G<\/jats:italic> has a ruling neighbor within <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\beta $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b2<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful <jats:italic>shattering<\/jats:italic> framework [BEPS JACM\u201916, Ghaffari SODA\u201919] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$G^k$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> in essentially the same time as they can be computed in <jats:italic>G<\/jats:italic>. Our main contribution is a deterministic <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${{\\,\\textrm{poly}\\,}}(k,\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>poly<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time algorithm for computing <jats:italic>k<\/jats:italic>-ruling sets of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$G^k$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, which (for k &gt; 1) improves exponentially on the current state-of-the-art runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. We also revisit the shattering algorithm for MIS [BEPS JACM\u201916] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA\u201916].<\/jats:p>","DOI":"10.1007\/s00446-025-00485-9","type":"journal-article","created":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T23:21:36Z","timestamp":1748128896000},"page":"261-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed symmetry breaking on power graphs via sparsification"],"prefix":"10.1007","volume":"38","author":[{"given":"Yannic","family":"Maus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saku","family":"Peltonen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,25]]},"reference":[{"issue":"15","key":"485_CR1","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1145\/22145.22146","volume":"11","author":"M Luby","year":"1986","unstructured":"Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing. 11(15), 1036\u20131053 (1986). https:\/\/doi.org\/10.1145\/22145.22146","journal-title":"SIAM Journal on Computing."},{"issue":"4","key":"485_CR2","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms. 7(4), 567\u2013583 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90019-2","journal-title":"Journal of Algorithms."},{"key":"485_CR3","doi-asserted-by":"publisher","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The Locality of Distributed Symmetry Breaking. J ACM. 63(3), (2016 jun). http:\/\/arxiv.org\/abs\/1202.1983 (arXiv v3). https:\/\/doi.org\/10.1145\/2903137","DOI":"10.1145\/2903137"},{"key":"485_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Luby, M., Goldberg, A.V., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: 30th Annual Symposium on Foundations of Computer Science. pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"485_CR5","doi-asserted-by":"publisher","unstructured":"Ghaffari, M.: An Improved Distributed Algorithm for Maximal Independent Set. In: Krauthgamer R, editor. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. SIAM; pp. 270\u2013277 (2016). Available from: https:\/\/doi.org\/10.1137\/1.9781611974331.ch20","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"485_CR6","doi-asserted-by":"publisher","unstructured":"Ghaffari, M.: Distributed Maximal Independent Set using Small Messages. In: Chan TM, editor. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. SIAM; pp. 805\u2013820 (2019). Available from: https:\/\/doi.org\/10.1137\/1.9781611975482.50","DOI":"10.1137\/1.9781611975482.50"},{"key":"485_CR7","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.tcs.2012.09.004","volume":"10","author":"J Schneider","year":"2013","unstructured":"Schneider, J., Elkin, M., Wattenhofer, R.: Symmetry breaking depending on the chromatic number or the neighborhood growth. Theoretical Computer Science. 10, 509 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.09.004","journal-title":"Theoretical Computer Science."},{"key":"485_CR8","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Maus, Y., Weidner, S.: Deterministic Distributed Ruling Sets of Line Graphs. In: Lotker Z, Patt-Shamir B, editors. Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma\u2019ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers. vol. 11085 of Lecture Notes in Computer Science. Springer; pp. 193\u2013208 (2018). Available from: https:\/\/doi.org\/10.1007\/978-3-030-01325-7_19","DOI":"10.1007\/978-3-030-01325-7_19"},{"key":"485_CR9","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Kuhn, F., Olivetti, D.: Distributed $$\\Delta $$-coloring plays hide-and-seek. In: Leonardi S, Gupta A, editors. STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022. ACM; pp. 464\u2013477 (2022). Available from: https:\/\/doi.org\/10.1145\/3519935.3520027","DOI":"10.1145\/3519935.3520027"},{"issue":"6","key":"485_CR10","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1023\/A:1012311216333","volume":"7","author":"SO Krumke","year":"2001","unstructured":"Krumke, S.O., Marathe, M.V., Ravi, S.S.: Models and Approximation Algorithms for Channel Assignment in Radio Networks. Wirel Networks. 7(6), 575\u2013584 (2001). https:\/\/doi.org\/10.1023\/A:1012311216333","journal-title":"Wirel Networks."},{"key":"485_CR11","doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M.M., Kuhn, F., Maus, Y.: Distance-2 Coloring in the CONGEST Model. In: Emek Y, Cachin C, editors. PODC \u201920: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020. ACM; pp. 233\u2013242 (2020). Available from: https:\/\/doi.org\/10.1145\/3382734.3405706","DOI":"10.1145\/3382734.3405706"},{"key":"485_CR12","doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M.M., Kuhn, F., Maus, Y., Nolin, A.: Coloring Fast Without Learning Your Neighbors\u2019 Colors. In: Attiya H, editor. 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference. vol. 179 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; pp. 39:1\u201339:17 (2020). Available from: https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.39","DOI":"10.4230\/LIPIcs.DISC.2020.39"},{"key":"485_CR13","doi-asserted-by":"crossref","unstructured":"Faour, S., Ghaffari, M., Grunau, C., Kuhn, F., Rozho\u010d, V.: Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA);. pp. 4409\u20134447. Available from: https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611977554.ch168","DOI":"10.1137\/1.9781611977554.ch168"},{"key":"485_CR14","doi-asserted-by":"publisher","unstructured":"Elkin, M., Matar, S. Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. In: Robinson P, Ellen F, editors. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. ACM; pp. 531\u2013540 (2019). Available from: https:\/\/doi.org\/10.1145\/3293611.3331635","DOI":"10.1145\/3293611.3331635"},{"issue":"1","key":"485_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in Distributed Graph Algorithms. SIAM Journal on Computing. 21(1), 193\u2013201 (1992). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM Journal on Computing."},{"key":"485_CR16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA (2000)"},{"key":"485_CR17","doi-asserted-by":"publisher","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths. SIAM J Comput. 50(3), (2021). https:\/\/doi.org\/10.1137\/16M1097808","DOI":"10.1137\/16M1097808"},{"key":"485_CR18","doi-asserted-by":"publisher","unstructured":"Kothapalli, K., Pemmaraju, S.V.: Super-Fast 3-Ruling Sets. In: D\u2019Souza D, Kavitha T, Radhakrishnan J, editors. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India. vol.\u00a018 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; pp. 136\u2013147 (2012). Available from: https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2012.136","DOI":"10.4230\/LIPIcs.FSTTCS.2012.136"},{"key":"485_CR19","doi-asserted-by":"publisher","unstructured":"Bisht, T., Kothapalli, K., Pemmaraju, S.V.: Brief announcement: Super-fast t-ruling sets. In: Halld\u00f3rsson MM, Dolev S, editors. ACM Symposium on Principles of Distributed Computing, PODC \u201914, Paris, France, July 15-18, 2014. ACM. pp. 379\u2013381 (2014). Available from: https:\/\/doi.org\/10.1145\/2611462.2611512","DOI":"10.1145\/2611462.2611512"},{"issue":"4","key":"485_CR20","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00446-021-00397-4","volume":"34","author":"M Ghaffari","year":"2021","unstructured":"Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y.: Improved distributed $$\\Delta $$-coloring. Distributed Comput. 34(4), 239\u2013258 (2021). https:\/\/doi.org\/10.1007\/s00446-021-00397-4","journal-title":"Distributed Comput."},{"key":"485_CR21","doi-asserted-by":"publisher","unstructured":"Fischer, M., Ghaffari, M.: Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma, and the Complexity Hierarchy. In: Richa AW, editor. 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria. vol.\u00a091 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; pp. 18:1\u201318:16 (2017). Available from: https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.18","DOI":"10.4230\/LIPIcs.DISC.2017.18"},{"key":"485_CR22","doi-asserted-by":"crossref","unstructured":"Fischer, M., Halld\u00f3rsson, M.M., Maus, Y.: Fast Distributed Brooks\u2019 Theorem. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA);. pp. 2567\u20132588. Available from: https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611977554.ch98","DOI":"10.1137\/1.9781611977554.ch98"},{"issue":"4","key":"485_CR23","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s00446-016-0287-6","volume":"30","author":"K Chung","year":"2017","unstructured":"Chung, K., Pettie, S., Su, H.: Distributed algorithms for the Lov\u00e1sz local lemma and graph coloring. Distributed Comput. 30(4), 261\u2013280 (2017). https:\/\/doi.org\/10.1007\/s00446-016-0287-6","journal-title":"Distributed Comput."},{"issue":"3","key":"485_CR24","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1137\/19M1249527","volume":"49","author":"Y Chang","year":"2020","unstructured":"Chang, Y., Li, W., Pettie, S.: Distributed ($$\\Delta $$+1)-Coloring via Ultrafast Graph Shattering. SIAM J Comput. 49(3), 497\u2013539 (2020). https:\/\/doi.org\/10.1137\/19M1249527","journal-title":"SIAM J Comput."},{"key":"485_CR25","doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M.M., Nolin, A.: Superfast Coloring in CONGEST via Efficient Color Sampling. In: Jurdzinski T, Schmid S, editors. Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Wroc\u0142aw, Poland, June 28 - July 1, 2021, Proceedings. vol. 12810 of Lecture Notes in Computer Science. Springer; pp. 68\u201383 (2021). Available from: https:\/\/doi.org\/10.1007\/978-3-030-79527-6_5","DOI":"10.1007\/978-3-030-79527-6_5"},{"key":"485_CR26","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: Hatami H, McKenzie P, King V, editors. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. ACM; pp. 784\u2013797 (2017). Available from: https:\/\/doi.org\/10.1145\/3055399.3055471","DOI":"10.1145\/3055399.3055471"},{"key":"485_CR27","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On Derandomizing Local Distributed Algorithms. In: Thorup M, editor. 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018. IEEE Computer Society; pp. 662\u2013673 (2018). Available from: https:\/\/doi.org\/10.1109\/FOCS.2018.00069","DOI":"10.1109\/FOCS.2018.00069"},{"key":"485_CR28","doi-asserted-by":"publisher","unstructured":"Rozho\u0148, V., Ghaffari, M.: Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020. New York, NY, USA: Association for Computing Machinery; pp. 350-363 (2020). Available from: https:\/\/doi.org\/10.1145\/3357713.3384298","DOI":"10.1145\/3357713.3384298"},{"key":"485_CR29","doi-asserted-by":"publisher","unstructured":"Bamberger, P., Kuhn, F., Maus, Y.: Efficient Deterministic Distributed Coloring with Small Bandwidth. In: Emek Y, Cachin C, editors. PODC \u201920: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020. ACM; pp. 243\u2013252 (2020). Available from: https:\/\/doi.org\/10.1145\/3382734.3404504","DOI":"10.1145\/3382734.3404504"},{"key":"485_CR30","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS); pp. 1009\u20131020 (2021)","DOI":"10.1109\/FOCS52979.2021.00101"},{"issue":"3\u20134","key":"485_CR31","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00446-020-00376-1","volume":"33","author":"K Censor-Hillel","year":"2020","unstructured":"Censor-Hillel, K., Parter, M., Schwartzman, G.: Derandomizing local distributed algorithms under bandwidth restrictions. Distributed Comput. 33(3\u20134), 349\u2013366 (2020). https:\/\/doi.org\/10.1007\/s00446-020-00376-1","journal-title":"Distributed Comput."},{"key":"485_CR32","doi-asserted-by":"publisher","unstructured":"Deurer, J., Kuhn, F., Maus, Y.: Deterministic Distributed Dominating Set Approximation in the CONGEST Model. In: Robinson P, Ellen F, editors. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. ACM. pp. 94\u2013103 (2019). Available from: https:\/\/doi.org\/10.1145\/3293611.3331626","DOI":"10.1145\/3293611.3331626"},{"key":"485_CR33","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Uitto, J.: Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA);. pp. 1636\u20131653. Available from: https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611975482.99","DOI":"10.1137\/1.9781611975482.99"},{"key":"485_CR34","doi-asserted-by":"publisher","unstructured":"Czumaj, A., Davies, P., Parter, M.: Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. SPAA \u201920. New York, NY, USA: Association for Computing Machinery; pp. 175-185 (2020). Available from: https:\/\/doi.org\/10.1145\/3350755.3400282","DOI":"10.1145\/3350755.3400282"},{"key":"485_CR35","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The Complexity of $$(\\Delta + 1)$$-Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). pp. 471\u2013480 (2019)","DOI":"10.1145\/3293611.3331607"},{"key":"485_CR36","doi-asserted-by":"publisher","unstructured":"Czumaj, A., Davies, P., Parter, M.: Improved Deterministic ($$\\Delta $$+1) Coloring in Low-Space MPC. In: Miller A, Censor-Hillel K, Korhonen JH, editors. PODC \u201921: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021. ACM; pp. 469\u2013479 (2021). Available from: https:\/\/doi.org\/10.1145\/3465084.3467937","DOI":"10.1145\/3465084.3467937"},{"key":"485_CR37","unstructured":"Balliu, A., Brandt, S., Fischer, M., Latypov, R., Maus, Y., Olivetti, D., et\u00a0al.: Exponential Speedup Over Locality in MPC with Optimal Memory. In: Proceedings of the International Symposium on Distributed Computing (DISC); pp. 9:1\u20139:21 (2022)"},{"key":"485_CR38","doi-asserted-by":"publisher","unstructured":"Ghaffari, M.: Distributed MIS via All-to-All Communication. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC \u201917. New York, NY, USA: Association for Computing Machinery; pp. 141-149 (2017). Available from: https:\/\/doi.org\/10.1145\/3087801.3087830","DOI":"10.1145\/3087801.3087830"},{"key":"485_CR39","doi-asserted-by":"publisher","unstructured":"Ghaffari, M.: Local Computation of Maximal Independent Set. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. IEEE; pp. 438\u2013449 (2022). Available from: https:\/\/doi.org\/10.1109\/FOCS54457.2022.00049","DOI":"10.1109\/FOCS54457.2022.00049"},{"issue":"5\u20136","key":"485_CR40","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00446-012-0174-8","volume":"26","author":"A Korman","year":"2013","unstructured":"Korman, A., Sereni, J., Viennot, L.: Toward more localized local algorithms: removing assumptions concerning global knowledge. Distributed Comput. 26(5\u20136), 289\u2013308 (2013). https:\/\/doi.org\/10.1007\/s00446-012-0174-8","journal-title":"Distributed Comput."},{"key":"485_CR41","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Grunau, C., Rozhon, V.: Improved Deterministic Network Decomposition. In: Marx D, editor. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021. SIAM; pp. 2904\u20132923 (2021). Available from: https:\/\/doi.org\/10.1137\/1.9781611976465.173","DOI":"10.1137\/1.9781611976465.173"},{"key":"485_CR42","doi-asserted-by":"publisher","unstructured":"Gfeller B, Vicari E.: A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing. PODC \u201907. New York, NY, USA: Association for Computing Machinery; pp. 53-60 (2007). Available from: https:\/\/doi.org\/10.1145\/1281100.1281111","DOI":"10.1145\/1281100.1281111"},{"key":"485_CR43","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Halld\u00f3rsson, M.M., Nolin, A.: Distributed Testing of Distance-k Colorings. In: Richa AW, Scheideler C, editors. Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings. vol. 12156 of Lecture Notes in Computer Science. Springer; pp. 275\u2013290 (2020). Available from: https:\/\/doi.org\/10.1007\/978-3-030-54921-3_16","DOI":"10.1007\/978-3-030-54921-3_16"},{"key":"485_CR44","doi-asserted-by":"publisher","unstructured":"Bar-Yehuda, R., Censor-Hillel, K., Maus, Y., Pai, S., Pemmaraju, S.V.: Distributed Approximation on Power Graphs. In: Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC \u201920. New York, NY, USA: Association for Computing Machinery; pp. 501-510 (2020). Available from: https:\/\/doi.org\/10.1145\/3382734.3405750","DOI":"10.1145\/3382734.3405750"},{"key":"485_CR45","doi-asserted-by":"publisher","unstructured":"Brandt, S.: An Automatic Speedup Theorem for Distributed Problems. In: Robinson P, Ellen F, editors. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). ACM; pp. 379\u2013388 (2019). Available from: https:\/\/doi.org\/10.1145\/3293611.3331611","DOI":"10.1145\/3293611.3331611"},{"issue":"1","key":"485_CR46","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1137\/20m1381770","volume":"51","author":"A Balliu","year":"2022","unstructured":"Balliu, A., Brandt, S., Olivetti, D.: Distributed Lower Bounds for Ruling Sets. SIAM J Comput. 51(1), 70\u2013115 (2022). https:\/\/doi.org\/10.1137\/20m1381770","journal-title":"SIAM J Comput."},{"key":"485_CR47","doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph Sketches: Sparsification, Spanners, and Subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. PODS \u201912. New York, NY, USA: Association for Computing Machinery; pp. 5-14 (2012). Available from: https:\/\/doi.org\/10.1145\/2213556.2213560","DOI":"10.1145\/2213556.2213560"},{"key":"485_CR48","doi-asserted-by":"publisher","unstructured":"Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. PODC \u201915. New York, NY, USA: Association for Computing Machinery; pp. 91-100 (2015). Available from: https:\/\/doi.org\/10.1145\/2767386.2767434","DOI":"10.1145\/2767386.2767434"},{"key":"485_CR49","doi-asserted-by":"publisher","unstructured":"Assadi, S., Chen, Y., Khanna, S.: Sublinear Algorithms for ($$\\Delta $$ + 1) Vertex Coloring. In: Chan TM, editor. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. SIAM; pp. 767\u2013786 (2019). Available from: https:\/\/doi.org\/10.1137\/1.9781611975482.48","DOI":"10.1137\/1.9781611975482.48"},{"key":"485_CR50","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Nowicki, K.: MST in O(1) Rounds of Congested Clique. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201918. USA: Society for Industrial and Applied Mathematics; pp. 2620-2632 (2018)","DOI":"10.1137\/1.9781611975031.167"},{"key":"485_CR51","doi-asserted-by":"publisher","unstructured":"Nowicki, K.: A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021. New York, NY, USA: Association for Computing Machinery; pp. 1154-1165 (2021). Available from: https:\/\/doi.org\/10.1145\/3406325.3451136","DOI":"10.1145\/3406325.3451136"},{"issue":"7","key":"485_CR52","doi-asserted-by":"publisher","first-page":"1980","DOI":"10.1007\/s00453-021-00816-9","volume":"83","author":"KJ Ahn","year":"2021","unstructured":"Ahn, K.J., Cormode, G., Guha, S., McGregor, A., Wirth, A.: Correlation Clustering in Data Streams. Algorithmica. 83(7), 1980\u20132017 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00816-9","journal-title":"Algorithmica."},{"key":"485_CR53","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovic, S., Rubinfeld, R.: Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC); pp. 129\u2013138 (2018)","DOI":"10.1145\/3212734.3212743"},{"key":"485_CR54","unstructured":"Alon, N., Assadi, S.: Palette Sparsification Beyond ($$\\Delta $$+1) Vertex Coloring. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020; pp. 6:1\u20136:22 (2020)"},{"key":"485_CR55","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Brief Announcement: Exponential Speed-up of Local Algorithms Using Non-Local Communication. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC); pp. 295-296 (2010)","DOI":"10.1145\/1835698.1835772"},{"key":"485_CR56","unstructured":"Dinitz, M., Nazari, Y.: Massively Parallel Approximate Distance Sketches. In: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019); pp. 35:1\u201335:17 (2020)"},{"key":"485_CR57","doi-asserted-by":"publisher","unstructured":"Dory, M., Fischer, O., Khoury, S., Leitersdorf, D.: Constant-Round Spanners and Shortest Paths in Congested Clique and MPC. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC\u201921. New York, NY, USA: Association for Computing Machinery; pp. 223-233 (2021). Available from: https:\/\/doi.org\/10.1145\/3465084.3467928","DOI":"10.1145\/3465084.3467928"},{"key":"485_CR58","unstructured":"Forster, S., Gr\u00f6sbacher, M., de\u00a0Vos, T.: An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. In: 25th International Conference on Principles of Distributed Systems (OPODIS 2021); pp. 16:1\u201316:17 (2022)"},{"key":"485_CR59","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Grunau, C., Haeupler, B., Ilchi, S., Rozho\u010d, V.: Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA);. pp. 2532\u20132566. Available from: https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611977554.ch97","DOI":"10.1137\/1.9781611977554.ch97"},{"key":"485_CR60","unstructured":"Vadhan, S.P.: Pseudorandomness. Foundations and trends in theoretical computer science. Now Publishers; (2012). Available from: https:\/\/books.google.fi\/books?id=iam4lAEACAAJ"},{"issue":"2","key":"485_CR61","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"JP Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding Bounds for Applications with Limited Independence. SIAM Journal on Discrete Mathematics. 8(2), 223\u2013250 (1995). https:\/\/doi.org\/10.1137\/S089548019223872X","journal-title":"SIAM Journal on Discrete Mathematics."},{"issue":"13","key":"485_CR62","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BF01303516","volume":"12","author":"N Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica. 12(13), 441\u2013454 (1993). https:\/\/doi.org\/10.1007\/BF01303516","journal-title":"Combinatorica."},{"key":"485_CR63","doi-asserted-by":"publisher","unstructured":"M\u00e9tivier, Y., Robson, J., Saheb-Djahromi, N., Zemmari, A.: An Optimal Bit Complexity Randomized Distributed MIS Algorithm. Distributed Computing. 01(23), 331\u2013340 (2011). https:\/\/doi.org\/10.1007\/s00446-010-0121-5","DOI":"10.1007\/s00446-010-0121-5"},{"key":"485_CR64","doi-asserted-by":"publisher","unstructured":"Maus, Y., Uitto, J.: Efficient CONGEST Algorithms for the Lov\u00e1sz Local Lemma. In: Gilbert S, editor. 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference). vol. 209 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; pp. 31:1\u201331:19 (2021). Available from: https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.31","DOI":"10.4230\/LIPIcs.DISC.2021.31"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00485-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00485-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00485-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T15:34:00Z","timestamp":1757172840000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00485-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,25]]},"references-count":64,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["485"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00485-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,5,25]]},"assertion":[{"value":"30 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Saku Peltonen is supported by the Academy of Finland, Grant 334238.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"The authors have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}