pith. sign in

arxiv: 2606.11974 · v1 · pith:46G7FXRUnew · submitted 2026-06-10 · 💻 cs.DS · cs.DC

Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity

Malte Baumecker , Rustam Latypov , Yannic Maus , Jara Uitto This is my paper

Pith reviewed 2026-06-27 08:16 UTC · model grok-4.3

classification 💻 cs.DS cs.DC
keywords distributed algorithmsruling setsarboricityLOCAL modelrandomized algorithmssymmetry breakingMPC model
0
0 comments X

The pith

Randomized algorithm computes 2-ruling sets in O(log log n) rounds on graphs with arboricity O(log log n).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a randomized LOCAL-model algorithm that with high probability produces a 2-ruling set in any n-node graph whose arboricity is bounded by O(log log n). The running time improves exponentially on all prior methods that combine existing ruling-set and coloring results, and it comes within a log-log-log factor of the known lower bound. The same work supplies a slower but still improved algorithm for arbitrary arboricity α and an O(log log log n)-round MPC algorithm that tolerates arboricity up to 2 to the power of a polynomial in log log n. Because β = 1 already requires Ω(√log n) rounds on arboricity-2 graphs, the choice of domination distance 2 is information-theoretically tight for any sub-polylogarithmic runtime.

Core claim

A randomized algorithm that w.h.p. computes a 2-ruling set on any n-node graph with bounded arboricity in O(log log n) rounds.

What carries the argument

Randomized procedure that repeatedly samples and prunes candidate nodes while exploiting the low-arboricity decomposition to keep the remaining degree small after each round.

If this is right

  • Graphs of arboricity up to O(log log n) admit exponentially faster distributed 2-ruling sets than general graphs.
  • For any constant or slowly growing α the new bound is Õ(log^{5/8} α + log^{5/3} log n).
  • In the MPC model the same sparsity regime yields an O(log log log n)-round algorithm.
  • β = 2 is the largest domination radius that can be achieved in log^{o(1)} n rounds on arboricity-2 graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sampling-and-pruning idea may yield fast ruling sets under other sparsity notions such as bounded degeneracy.
  • One could attempt to derandomize the procedure while preserving the O(log log n) bound.
  • The MPC result suggests that low-arboricity instances are also easy for massively parallel symmetry breaking beyond the LOCAL model.

Load-bearing premise

The input graph has arboricity at most O(log log n).

What would settle it

An n-node graph of arboricity O(log log n) on which every 2-ruling-set algorithm requires ω(log log n) rounds with high probability.

Figures

Figures reproduced from arXiv: 2606.11974 by Jara Uitto, Malte Baumecker, Rustam Latypov, Yannic Maus.

Figure 1
Figure 1. Figure 1: Distributed algorithms for ruling sets: upper bounds are shown as dots (fill pattern indi [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: On the left, we consider the case of many low-degree neighbors (discussed in the intro). [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A three-vertex example with independent candidate set [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗
read the original abstract

Given a graph $G=(V,E)$, a $\beta$-ruling set is a subset of nodes $S\subseteq V$ that is independent, and each node in $V$ is at distance at most $\beta$ from some node in $S$. In this paper, we present almost optimal distributed algorithms for finding $2$-ruling sets in the classical \LOCAL model. Our main contribution is a randomized algorithm that w.h.p.\ computes a $2$-ruling set on any $n$-node graph with bounded arboricity in $O(\log \log n)$ rounds. In fact, the algorithm works up to arboricity $O(\log\log n)$, improves exponentially over the prior state of the art that can be achieved by combining [Barenboim, Elkin, Pettie, Schneider; JACM'16], [Ghaffari; SODA'16], and [Bisht, Kothapalli and Pemmaraju; PODC'14], and nearly matches the lower bound of $\Omega(\log \log n / \log \log \log n)$ [Balliu, Brandt, Kuhn, Olivetti; FOCS'20]. The domination parameter $\beta=2$ is optimal for algorithms with runtime $\log^{o(1)}n$: on graphs with arboricity $2$, there is a lower bound of $\Omega(\sqrt{\log n})$ rounds for MIS (i.e., $\beta = 1$) [Khoury, Schild; FOCS'25]. Additionally, we obtain improved algorithms for larger arboricity. For general graphs with arboricity $\alpha$, we present a randomized algorithm that computes a $2$-ruling set in $\widetilde{O}(\log^{5/8} \alpha +\log^{5/3} \log n)$ rounds. This improves exponentially over the state of the art for a large range of non-constant arboricity. Our techniques extend beyond distributed computing. We present an $O(\log \log \log n)$-round algorithm in the low-space Massively Parallel Computation (\mpc) model that w.h.p.\ computes a $2$-ruling set on any graph with arboricity up to $2^{poly (\log \log n)}$, improving exponentially over the state of the art from [Kothapalli, Pai, Pemmaraju; FSTTCS'20] combined with [Fischer, Giliberti, Grunau; SPAA'23].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper presents randomized distributed algorithms for computing 2-ruling sets (independent dominating sets with distance-2 domination) in the LOCAL model. The central claim is an O(log log n)-round w.h.p. algorithm for any n-node graph with arboricity up to O(log log n), which improves exponentially over the combination of prior results from Barenboim et al. (JACM'16), Ghaffari (SODA'16), and Bisht et al. (PODC'14) and nearly matches the Ω(log log n / log log log n) lower bound of Balliu et al. (FOCS'20). Additional results include a ilde{O}(log^{5/8} α + log^{5/3} log n)-round algorithm for general arboricity α and an O(log log log n)-round MPC algorithm for arboricity up to 2^{poly(log log n)}.

Significance. If the claims hold, the result is significant: it supplies the first sub-polylogarithmic-time algorithm for 2-ruling sets that is near-optimal in the low-arboricity regime, correctly distinguishes the β=2 case from the stronger MIS lower bound on arboricity-2 graphs (Khoury-Schild FOCS'25), and gives exponential improvements for both the LOCAL and MPC models. The explicit runtime comparisons to independent prior work and the cited lower bound, together with the parameter-free form of the O(log log n) bound relative to the lower bound, strengthen the contribution.

minor comments (2)
  1. [Abstract] The abstract states the O(log log n) bound holds 'up to arboricity O(log log n)' but does not explicitly restate the precise dependence on α in the general-arboricity result; adding a single sentence in the introduction clarifying the transition point between the two regimes would improve readability.
  2. [Abstract] The MPC result is stated for arboricity up to 2^{poly(log log n)}; a brief remark on whether the same technique yields a smooth trade-off for intermediate arboricity values would be helpful.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the accurate summary of our results, and the recommendation to accept the paper. We appreciate the recognition of the exponential improvements and the near-optimality in the low-arboricity regime.

Circularity Check

0 steps flagged

No circularity; derivation self-contained against external benchmarks

full rationale

The paper presents a new randomized LOCAL-model algorithm for 2-ruling sets whose O(log log n) runtime (w.h.p.) on graphs with arboricity O(log log n) is derived from the input sparsity parameter and standard concentration arguments; it is compared to an independent lower bound of Ω(log log n / log log log n) from Balliu et al. FOCS'20 and improves on combinations of prior independent results (Barenboim et al. JACM'16, Ghaffari SODA'16, Bisht et al. PODC'14). The β=2 optimality distinction versus the MIS lower bound on arboricity-2 graphs is likewise external. No equation reduces the runtime claim to a fitted parameter, self-citation chain, or renamed input; the MPC extension follows the same pattern. The derivation chain is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard LOCAL communication model and high-probability analysis; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • domain assumption LOCAL model: synchronous rounds with neighbor communication only
    Standard assumption invoked for all runtime claims
  • standard math w.h.p. success probability 1-1/poly(n)
    Common probabilistic guarantee stated for the main algorithm

pith-pipeline@v0.9.1-grok · 6018 in / 1335 out tokens · 23051 ms · 2026-06-27T08:16:16.427116+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

69 extracted references · 44 canonical work pages

  1. [1]

    A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.Journal of Algorithms, 7(4):567–583, 1986

    Noga Alon, Lásló Babai, and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.Journal of Algorithms, 7(4):567–583, 1986

    1986

  2. [2]

    Ruling Sets in Random Order and Adversarial Streams

    Sepehr Assadi and Aditi Dudeja. Ruling Sets in Random Order and Adversarial Streams. In the International Symposium on Distributed Computing (DISC), pages 6:1–6:18, 2021.doi: 10.4230/LIPIcs.DISC.2021.6

    work page doi:10.4230/lipics.disc.2021.6 2021

  3. [3]

    Goldberg, Michael Luby, and Serge A

    Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network De- composition and Locality in Distributed Computation. Inthe Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 364–369, 1989

    1989

  4. [4]

    Lower Bounds for Maximal Matchings and Maximal Independent Sets

    Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower Bounds for Maximal Matchings and Maximal Independent Sets. Inthe Pro- ceedings of the Symposium on Foundations of Computer Science (FOCS), 2019

    2019

  5. [5]

    Distributed∆-coloring plays hide-and-seek

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed∆-coloring plays hide-and-seek. InProc. 54th ACM Symp. on Theory of Computing (STOC), 2022

    2022

  6. [6]

    Near-linear Size Hypergraph Cut Sparsifiers , booktitle =

    Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed Lower Bounds for Ruling Sets. Inthe Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 365–376, 2020.doi:10.1109/FOCS46700.2020.00042

    work page doi:10.1109/focs46700.2020.00042 2020

  7. [7]

    Distributed lower bounds for ruling sets.SIAM J

    Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets.SIAM J. Comput., 51(1):70–115, 2022. URL:https://doi.org/10.1137/20m1381770, doi:10.1137/20M1381770

    work page doi:10.1137/20m1381770 2022

  8. [8]

    On the Impact of Identifiers on Local Decision

    Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. Node and edge averaged complexities of local graph problems. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 4–14, New York, NY, USA, 2022. Association for Computing Machinery.doi:10.1145/3519270.3538419

    work page doi:10.1145/3519270.3538419 2022

  9. [9]

    Barenboim and M

    L. Barenboim and M. Elkin. Sublogarithmic distributed mis algorithm for sparse graphs us- ing nash-williams decomposition.Distributed Computing, 22(5):363–379, 2010.doi:10.1007/ s00446-009-0088-2

    2010

  10. [10]

    Locally-iterative distributed(δ+ 1)- coloring and applications.J

    Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed(δ+ 1)- coloring and applications.J. ACM, 69(1), December 2021.doi:10.1145/3486625

    work page doi:10.1145/3486625 2021

  11. [11]

    Distributed(δ+ 1)-coloring in linear (in δ) time.SIAM Journal on Computing, 43(1):72–95, 2014.arXiv:https://doi.org/10.1137/ 12088848X,doi:10.1137/12088848X

    Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed(δ+ 1)-coloring in linear (in δ) time.SIAM Journal on Computing, 43(1):72–95, 2014.arXiv:https://doi.org/10.1137/ 12088848X,doi:10.1137/12088848X

    work page doi:10.1137/12088848x 2014

  12. [12]

    The Locality of Dis- tributed Symmetry Breaking.Journal of the ACM, 63(3):20:1–20:45, 2016

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The Locality of Dis- tributed Symmetry Breaking.Journal of the ACM, 63(3):20:1–20:45, 2016

    2016

  13. [13]

    Nearly-optimal distributed ruling sets for trees and high-girth graphs

    Malte Baumecker, Yannic Maus, and Jara Uitto. Nearly-optimal distributed ruling sets for trees and high-girth graphs. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 88–98, New York, NY, USA, 2025. Association for Computing Machinery.doi:10.1145/3732772.3733547. 22

    work page doi:10.1145/3732772.3733547 2025

  14. [14]

    Communication Steps for Parallel Query Processing.the Journal of the ACM, 64(6), 2017.doi:10.1145/3125644

    Paul Beame, Paraschos Koutris, and Dan Suciu. Communication Steps for Parallel Query Processing.the Journal of the ACM, 64(6), 2017.doi:10.1145/3125644

    work page doi:10.1145/3125644 2017

  15. [15]

    Brief announcement: Super-fast t- ruling sets

    Tushar Bisht, Kishore Kothapalli, and Sriram Pemmaraju. Brief announcement: Super-fast t- ruling sets. Inthe Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 379–381, 2014.doi:10.1145/2611462.2611512

    work page doi:10.1145/2611462.2611512 2014

  16. [16]

    Massively Parallel Correla- tion Clustering in Bounded Arboricity Graphs

    Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto. Massively Parallel Correla- tion Clustering in Bounded Arboricity Graphs. In Seth Gilbert, editor,35th International Symposium on Distributed Computing (DISC 2021), volume 209 ofLeibniz International Pro- ceedings in Informatics (LIPIcs), pages 15:1–15:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl...

    work page doi:10.4230/lipics.disc.2021.15 2021

  17. [18]

    Time and space optimal massively parallel algorithm for the 2-ruling set problem

    Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and space optimal massively parallel algorithm for the 2-ruling set problem. In Rotem Oshman, editor,37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy, vol- ume 281 ofLIPIcs, pages 11:1–11:12. Schloss Dagstuhl - Leibniz-Zentrum für Informati...

    work page doi:10.4230/lipics.disc.2023.11 2023

  18. [19]

    URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.110, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.110,doi:10.1137/1

    Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quan- rud, Eva Rotenberg, and Chris Schwiegelshohn.Adaptive Out-Orientations with Applications, pages 3062–3088. URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.110, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.110,doi:10.1137/1. 9781611977912.110

    work page doi:10.1137/1.9781611977912.110

  19. [20]

    Breuckmann and Chinmay Nirkhe , editor =

    Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dy- namic colouring of sparse graphs. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1201–1214, New York, NY, USA, 2023. Association for Computing Machinery.doi:10.1145/3564246.3585111

    work page doi:10.1145/3564246.3585111 2023

  20. [21]

    URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611976496.21,arXiv:https:// epubs.siam.org/doi/pdf/10.1137/1.9781611976496.21,doi:10.1137/1.9781611976496

    Corinna Coupette and Christoph Lenzen.A Breezing Proof of the KMW Bound, pages 184–195. URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611976496.21,arXiv:https:// epubs.siam.org/doi/pdf/10.1137/1.9781611976496.21,doi:10.1137/1.9781611976496. 21

    work page doi:10.1137/1.9781611976496.21

  21. [22]

    Graph sparsification for derandomizing mas- sively parallel computation with low space

    Artur Czumaj, Peter Davies, and Merav Parter. Graph sparsification for derandomizing mas- sively parallel computation with low space. InProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, page 175–185, New York, NY, USA,

  22. [23]

    Association for Computing Machinery.doi:10.1145/3350755.3400282

    work page doi:10.1145/3350755.3400282

  23. [24]

    Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,

    Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clus- ters.Communications of the ACM, pages 107–113, 2008.doi:10.1145/1327452.1327492

    work page doi:10.1145/1327452.1327492 2008

  24. [25]

    Near-optimal distributed dominating set in bounded arboricity graphs.Distributed Computing, 37(4):387–398, May 2023.doi:10.1007/ s00446-023-00447-z

    Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs.Distributed Computing, 37(4):387–398, May 2023.doi:10.1007/ s00446-023-00447-z. 23

    2023

  25. [26]

    URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.96, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.96,doi:10.1137/1

    Talya Eden, Saleet Mossel, and Dana Ron.Approximating the Arboricity in Sublinear Time, pages 2404–2425. URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.96, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.96,doi:10.1137/1. 9781611977073.96

    work page doi:10.1137/1.9781611977073.96

  26. [27]

    Seshadhri.Faster sublinear approximation of the number of k-cliques in low-arboricity graphs, pages 1467–1478

    Talya Eden, Dana Ron, and C. Seshadhri.Faster sublinear approximation of the number of k-cliques in low-arboricity graphs, pages 1467–1478. 2020. URL:https://epubs.siam. org/doi/abs/10.1137/1.9781611975994.89,arXiv:https://epubs.siam.org/doi/pdf/10. 1137/1.9781611975994.89,doi:10.1137/1.9781611975994.89

    work page doi:10.1137/1.9781611975994.89 2020

  27. [28]

    Esary, Frank Proschan, and David W

    James D. Esary, Frank Proschan, and David W. Walkup. Association of random variables, with applications.The Annals of Mathematical Statistics, 38(5):1466–1474, 1967.doi:10. 1214/aoms/1177698701

    arXiv 1967

  28. [29]

    Brief Announcement: Faster CONGEST Approximation Al- gorithms for Maximum Weighted Independent Set in Sparse Graphs

    Salwa Faour and Fabian Kuhn. Brief Announcement: Faster CONGEST Approximation Al- gorithms for Maximum Weighted Independent Set in Sparse Graphs. In Dariusz R. Kowalski, editor,39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages54:1–54:7, Dagstuhl, Germany, 2025....

    work page doi:10.4230/lipics.disc.2025.54 2025

  29. [30]

    Deterministic massively parallel sym- metry breaking for sparse graphs

    Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Deterministic massively parallel sym- metry breaking for sparse graphs. InProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 89–100, New York, NY, USA, 2023. Association for Computing Machinery.doi:10.1145/3558481.3591081

    work page doi:10.1145/3558481.3591081 2023

  30. [31]

    Atailboundforread- k families of functions.Random Structures & Algorithms, 47(1):99–108, 2015

    DmitryGavinsky, ShacharLovett, MichaelSaks, andSrikanthSrinivasan. Atailboundforread- k families of functions.Random Structures & Algorithms, 47(1):99–108, 2015. URL:https:// onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20532,arXiv:https://onlinelibrary. wiley.com/doi/pdf/10.1002/rsa.20532,doi:10.1002/rsa.20532

    work page doi:10.1002/rsa.20532 2015

  31. [32]

    Gfeller and E

    B. Gfeller and E. Vicari. A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. Inthe Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 53–60, 2007

    2007

  32. [33]

    An Improved Distributed Algorithm for Maximal Independent Set

    Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. Inthe Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270–277, 2016

    2016

  33. [34]

    Dynamic o(arboricity) coloring in polylogarithmic worst-case time

    Mohsen Ghaffari and Christoph Grunau. Dynamic o(arboricity) coloring in polylogarithmic worst-case time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1184–1191, New York, NY, USA, 2024. Association for Computing Machin- ery.doi:10.1145/3618260.3649782

    work page doi:10.1145/3618260.3649782 2024

  34. [35]

    Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta

    Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. Inthe Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 2148–2179, 2024.doi:10.1109/FOCS61266.2024.00007

    work page doi:10.1109/focs61266.2024.00007 2024

  35. [36]

    Improved distributed network decomposition, hitting sets, and spanners, via derandomiza- tion

    Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhon. Improved distributed network decomposition, hitting sets, and spanners, via derandomiza- tion. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM- SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, 24 pages ...

    work page doi:10.1137/1.9781611977554.ch97 2023

  36. [37]

    Improved MPC Algorithms for MIS, Match- ing, and Coloring on Trees and Beyond

    Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC Algorithms for MIS, Match- ing, and Coloring on Trees and Beyond. In Hagit Attiya, editor,34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibni...

    work page doi:10.4230/lipics.disc.2020.34 2020

  37. [38]

    Improved distributed delta- coloring

    Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. Improved distributed delta- coloring. Inthe Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 427–436, 2018. URL:https://dl.acm.org/citation.cfm?id=3212764

    2018

  38. [39]

    Mohsen Ghaffari and Jara Uitto.Sparsifying Distributed Algorithms with Ramifications in Mas- sively Parallel Computation and Centralized Local Computation, pages 1636–1653. 2019. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.99,arXiv:https://epubs. siam.org/doi/pdf/10.1137/1.9781611975482.99,doi:10.1137/1.9781611975482.99

    work page doi:10.1137/1.9781611975482.99 2019

  39. [40]

    Massively Parallel Ruling Set Made Deterministic

    Jeff Giliberti and Zahra Parsaeian. Massively Parallel Ruling Set Made Deterministic. In Dan Alistarh, editor,38th International Symposium on Distributed Computing (DISC 2024), volume 319 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 29:1– 29:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://...

    work page doi:10.4230/lipics.disc.2024.29 2024

  40. [41]

    Henzinger, S

    M. Henzinger, S. Krinninger, and D. Nanongkai. A deterministic almost-tight dis- tributed algorithm for approximating single-source shortest paths. InProc. 48th ACM Symp. on Theory of Computing (STOC), pages 489–498, 2016

    2016

  41. [42]

    Iliopoulos and N

    G. Iliopoulos and N. Balakrishnan. Conditional independence of blocked ordered data.Statis- tics and Probability Letters, 79(8):1008–1015, 2009. URL:https://www.sciencedirect.com/ science/article/pii/S0167715208005683,doi:10.1016/j.spl.2008.12.005

    work page doi:10.1016/j.spl.2008.12.005 2009

  42. [43]

    Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks.ACM SIGOPS Operating Systems Review, pages 59–72, 2007.doi:10.1145/1272996.1273005

    Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks.ACM SIGOPS Operating Systems Review, pages 59–72, 2007.doi:10.1145/1272996.1273005

    work page doi:10.1145/1272996.1273005 2007

  43. [44]

    Fast deterministic massively parallel ruling sets algorithms

    Hongyan Ji, Kishore Kothapalli, Sriram V Pemmaraju, and Ajitanshu Singh. Fast deterministic massively parallel ruling sets algorithms. InProceedings of the 26th International Conference on Distributed Computing and Networking, ICDCN ’25, page 152–160, New York, NY, USA,

  44. [45]

    Association for Computing Machinery.doi:10.1145/3700838.3700872

    work page doi:10.1145/3700838.3700872

  45. [46]

    Karloff, Siddharth Suri, and Sergei Vassilvitskii

    Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. Inthe Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938–948, 2010.doi:10.1137/1.9781611973075.76

    work page doi:10.1137/1.9781611973075.76 2010

  46. [47]

    Breaking barriers for distributed mis by faster degree reduction,

    Seri Khoury and Aaron Schild. Breaking barriers for distributed mis by faster degree reduction,

  47. [48]

    URL:https://arxiv.org/abs/2505.15652,arXiv:2505.15652

    arXiv

  48. [49]

    Round elimination via self-reduction: Closing gaps for distributed maximal matching, 2025

    Seri Khoury and Aaron Schild. Round elimination via self-reduction: Closing gaps for distributed maximal matching, 2025. URL:https://arxiv.org/abs/2505.15654,arXiv: 2505.15654. 25

    arXiv 2025

  49. [50]

    Sparse matrix multiplication and triangle listing in the congested clique model

    Kishore Kothapalli, Shreyas Pai, and Sriram V. Pemmaraju. Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model. In Nitin Saxena and Sunil Simon, editors, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Com- puter Science (FSTTCS 2020), volume 182 ofLeibniz International Proceedings in Informatics (LI...

    work page doi:10.4230/lipics 2020

  50. [51]

    Super-Fast 3-Ruling Sets

    Kishore Kothapalli and Sriram Pemmaraju. Super-Fast 3-Ruling Sets. pages 136–147, 2012. doi:10.4230/LIPIcs.FSTTCS.2012.136

    work page doi:10.4230/lipics.fsttcs.2012.136 2012

  51. [52]

    F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds. J. of the ACM, 63(2), 2016

    2016

  52. [53]

    Deterministic distributed ruling sets of line graphs

    Fabian Kuhn, Yannic Maus, and Simon Weidner. Deterministic distributed ruling sets of line graphs. In Zvi Lotker and Boaz Patt-Shamir, editors,Structural Information and Communica- tion Complexity - 25th International Colloquium, SIROCCO 2018, Ma’ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, volume 11085 ofLecture Notes in Computer Sci...

    work page doi:10.1007/978-3-030-01325-7 2018

  53. [54]

    Brief Announcement: Exponential Speed-up of Local Algorithms Using Non-Local Communication

    Christoph Lenzen and Roger Wattenhofer. Brief Announcement: Exponential Speed-up of Local Algorithms Using Non-Local Communication. Inthe Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 295–296, 2010.doi:10.1145/1835698. 1835772

    work page doi:10.1145/1835698 2010

  54. [55]

    Minimum dominating set approximation in graphs of bounded arboricity

    Christoph Lenzen and Roger Wattenhofer. Minimum dominating set approximation in graphs of bounded arboricity. In Nancy A. Lynch and Alexander A. Shvartsman, editors,Distributed Computing, pages 510–524, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

    2010

  55. [56]

    Locality in Distributed Graph Algorithms.SIAM Journal on Computing, 21(1):193–201, 1992

    Nati Linial. Locality in Distributed Graph Algorithms.SIAM Journal on Computing, 21(1):193–201, 1992

    1992

  56. [57]

    M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem.SIAM Journal on Computing, 15:1036–1053, 1986

    1986

  57. [58]

    Distributed graph coloring made easy

    Yannic Maus. Distributed graph coloring made easy. In Kunal Agrawal and Yossi Azar, editors, SPAA ’21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 362–372. ACM, 2021.doi:10.1145/3409964.3461804

    work page doi:10.1145/3409964.3461804 2021

  58. [59]

    Distributed symmetry breaking on power graphs via sparsification

    Yannic Maus, Saku Peltonen, and Jara Uitto. Distributed symmetry breaking on power graphs via sparsification. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC ’23, page 157–167, New York, NY, USA, 2023. Association for Computing Machinery.doi:10.1145/3583668.3594579

    work page doi:10.1145/3583668.3594579 2023

  59. [60]

    Algorithms for the Minimum Domi- nating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial

    Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the Minimum Domi- nating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. In Seth Gilbert, editor,35th International Symposium on Distributed Computing (DISC 2021), volume 209 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 33:1– 33:19, Dagstuhl, Ger...

    work page doi:10.4230/lipics.disc.2021.33 2021

  60. [61]

    Pemmaraju, Talal Riaz, and Peter Robinson

    Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In Andréa Richa, editor,31st International Symposium on Distributed Computing (DISC 2017), volume 91 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 38:1– 38...

    work page doi:10.4230/lipics.disc.2017.38 2017

  61. [62]

    Pemmaraju

    Shreyas Pai and Sriram V. Pemmaraju. Brief Announcement: Deterministic Massively Par- allel Algorithms for Ruling Sets. Inthe Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 366–368, 2022.doi:10.1145/3519270.3538472

    work page doi:10.1145/3519270.3538472 2022

  62. [63]

    Distributed computing: A locality-sensitive approach

    David Peleg. Distributed computing: A locality-sensitive approach. 1987. URL:https: //api.semanticscholar.org/CorpusID:58843423

    1987

  63. [64]

    Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

    Sriram Pemmaraju and Talal Riaz. Using Read-k Inequalities to Analyze a Distributed MIS Algorithm. In Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone, edi- tors,20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:17, Dagstuhl, Germany,...

    work page doi:10.4230/lipics.opodis.2016.9 2016

  64. [65]

    Polylogarithmic-time Deterministic Network Decompo- sition and Distributed Derandomization

    Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time Deterministic Network Decompo- sition and Distributed Derandomization. Inthe Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 350–363, 2020

    2020

  65. [67]

    Symmetry breaking depending on the chromatic number or the neighborhood growth.Theor

    Johannes Schneider, Michael Elkin, and Roger Wattenhofer. Symmetry breaking depending on the chromatic number or the neighborhood growth.Theor. Comput. Sci., 509:40–50, 2013. doi:10.1016/j.tcs.2012.09.004

    work page doi:10.1016/j.tcs.2012.09.004 2013

  66. [68]

    A new technique for distributed symmetry breaking

    Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. Inthe Proceedings of the ACM Symposium on Principles of Distributed Comput- ing (PODC), pages 257–266, 2010.doi:10.1145/1835698.1835760

    work page doi:10.1145/1835698.1835760 2010

  67. [69]

    O’Reilly Media, Inc., 2009

    Tom White.Hadoop: The Definitive Guide. O’Reilly Media, Inc., 2009

    2009

  68. [70]

    Franklin, Scott Shenker, and Ion Stoica

    Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: ClusterComputing with WorkingSets. Inthe Proceedings of the USENIX Conference on Hot Topics in Cloud Computing (HotCloud), page 10, 2010.doi:10.5555/1863103.1863113

    work page doi:10.5555/1863103.1863113 2010

  69. [71]

    Probabilistic methods in combinatorics: Lecture 15, correlation in- equalities

    Yufei Zhao. Probabilistic methods in combinatorics: Lecture 15, correlation in- equalities. MIT OpenCourseWare, 18.226 Probabilistic Methods in Combina- torics, 2022. Accessed: 2026-01-06. URL:https://ocw.mit.edu/courses/ 18-226-probabilistic-methods-in-combinatorics-fall-2022/resources/mit18_226_ f22_lec15_pdf/. 27 A Extended Related Work Dominationβ Run...

    2022