Pith. sign in

REVIEW 5 minor 90 references

Distributed Symmetry Breaking on Hyperbolic Random Graphs

T0 review · 0 major / 5 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read MIS and maximal matching stay super-constant on hyperbolic random graphs, even though colouring collapses to two rounds.

desk verdict Solid, self-contained complexity separation for MIS/MM on HRGs: new geometric shattering upper bounds and a tree-embedding lower bound that cleanly separates them from 2-round colouring. read the letter →

arxiv 2607.09170 v1 pith:HTG3GSAM submitted 2026-07-10 cs.DC math.PR

Yannic Maus , Janosch Ruff , Sonia Simons , George Skretas This is my paper · ORCID
classification cs.DCmath.PR
keywords hyperbolicrandomgraphsmaximalindependentsetmatchingLOCALmodelCONGESTgeometricshatteringdistributedsymmetrybreakingd-arytrees
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Hyperbolic random graphs are a standard generative model for power-law networks with high clustering. Prior work showed that Δ+1 colouring can be finished in only two rounds on such graphs. This paper shows that the related symmetry-breaking tasks of maximal independent set and maximal matching do not enjoy the same collapse: both still require Ω(log log n / log log log n) rounds on the giant component. The lower bound is obtained by proving that these graphs contain many large induced d-ary trees attached by a single cut edge, so classical tree lower bounds transfer. Matching upper bounds of Õ(log^{5/3} log n) rounds (LOCAL) and Õ(log^{3} log n) rounds (CONGEST) are obtained by a two-step geometric shattering procedure that isolates only polylog-size residual components. When nodes also know their hyperbolic coordinates, maximal matching further drops to O(log log log n) rounds. The contrast with colouring therefore separates the complexity of different symmetry-breaking problems even on the same realistic network model.

What carries the argument

Geometric construction of polynomially many induced d-ary trees of height Θ(log log n / log log log n) and degree Θ(log log n), each attached to the giant component by a unique cut edge at the root; these trees let classical round-elimination lower bounds on regular trees be lifted to hyperbolic random graphs.

What would settle it

Either exhibit an o(log log n / log log log n)-round randomised LOCAL algorithm that succeeds with high probability on the giant component of every sufficiently large threshold hyperbolic random graph, or prove that such graphs contain no induced d-ary trees of the claimed height and degree.

Watch

Extended reading notes

Core claim

Asymptotically almost surely, any randomised LOCAL algorithm for MIS or maximal matching on the giant component of a threshold hyperbolic random graph needs Ω(log log n / log log log n) rounds, while both problems can be solved in Õ(log^{5/3} log n) LOCAL rounds (and Õ(log^{3} log n) CONGEST rounds) by constant-round geometric shattering followed by deterministic cleanup of the residual components.

Load-bearing premise

An algorithm that runs for fewer rounds than roughly one-hundredth of the constructed tree height cannot notice the single cut edge that joins the tree to the rest of the giant component, so the tree lower bound still applies.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies distributed MIS and maximal matching on threshold hyperbolic random graphs. It proves that both problems require Ω(log log n / log log log n) rounds a.a.s. on the giant component in the LOCAL model (Theorem 2), by constructing polynomially many induced d-ary trees of height θ(log_d log n) attached by a single cut-edge (Theorem 18 / Corollary 23) and transferring known tree lower bounds via a careful coupling (Lemma 24). Matching upper bounds of Õ(log^{5/3} log n) LOCAL and Õ(log^{3} log n) CONGEST are obtained by a constant-round geometric shattering procedure that realises angular separators (Theorem 1, Propositions 14 and 17). When nodes know their hyperbolic coordinates, MM improves further to O(log log log n) CONGEST rounds (Theorem 3).

Significance. The work cleanly separates the complexity of MIS/MM from that of Δ+1-colouring on the same generative model, showing that the dramatic constant-round colouring result of Maus–Ruff does not extend to all classical symmetry-breaking problems. The geometric tree-embedding theorem is of independent structural interest and supplies a reusable lower-bound transfer technique for other locally checkable problems on HRGs. The shattering analysis is self-contained and does not rely on the flawed off-the-shelf shattering arguments recently identified in the literature. The embedding-aware separation for MM is a clean illustration that geometric side information can beat pure combinatorial lower bounds. Full proofs, concentration arguments, and an explicit generalisation of round-elimination to arbitrary error probability (Appendix C) are supplied.

minor comments (5)
  1. [Abstract / Theorem 1] In the abstract and Theorem 1 the CONGEST bound is written Õ(log^{3} log n); the footnote and the MM analysis claim the slightly stronger O(log^{3} log n). Align the statements.
  2. [Section 7, Tiling] The constant 40 appearing in the tiling (Eq. (26) and Lemma 27) is chosen for convenience; a short remark that any sufficiently large constant works would help readers who wish to re-use the tiling.
  3. [Figure 1] Figure 1 caption refers to “Theorem 3 (MM)” and “Theorem 3 (MIS)”; the figure itself would be clearer if the two embedding-aware bounds were drawn with distinct markers.
  4. [Section 4, Lemma 9] Lemma 9 is used repeatedly; a one-sentence geometric intuition (shared neighbour of larger radius forces a triangle) would make later applications easier to follow.
  5. [Appendix A] In Appendix A the parameter ε = (1-1/(2α))/(2t(t+2)) is tuned so that the residual degree stays polynomial after any constant number of Luby rounds; a brief numerical example for a concrete α would make the calculation more transparent.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; geometric tree construction and shattering are independent of the imported external lower-bound sequences, with only non-load-bearing self-citation to the authors' prior colouring result.

full rationale

The paper's central claims (Theorems 1–2) rest on two independent pillars that do not reduce to their own inputs by construction. Upper bounds (Propositions 14 and 17) follow from a constant-round geometric shattering argument that uses only standard Chernoff/Poisson concentration on the HRG measure (Lemmas 6–8) together with off-the-shelf deterministic solvers of Ghaffari–Grunau and Faour et al.; no parameters are fitted to the target runtime. Lower bounds are obtained by an a.a.s. geometric embedding of polynomially many induced d-ary trees of controlled height and degree (Theorem 18 / Corollary 23, via the explicit box construction of Definition 19 and the niceness probability of Lemma 21), followed by a coupling transfer (Lemma 24) that maps any fast HRG algorithm onto an abstract regular tree, and only then by invoking the external round-elimination sequences of Balliu et al. (Lemma 25, extended in Appendix C to general error probability). The sole self-citation of substance is the authors' own SODA'26 colouring result, used only for contrast and not as a premise of either the shattering or the tree construction. No equation equates a claimed prediction to a fitted quantity, no uniqueness theorem is imported from the same authors to forbid alternatives, and no ansatz is smuggled via citation. The derivation is therefore self-contained against external benchmarks.

Assumptions & free parameters 2 free parameters · 4 assumptions · 2 invented entities

The central claims rest on the standard Poissonised threshold HRG model (parameters α∈(1/2,1), C∈ℝ), classical concentration inequalities, and previously published round-elimination lower bounds for trees. The only paper-specific inventions are the geometric “boxes” and “nice sectors” used to embed the trees, and the particular activation annuli chosen for shattering; both are fully defined and analysed inside the manuscript.

free parameters (2)
  • activation-degree thresholds (log^4 n, log^{3/2} n, …)
    Concrete polylogarithmic cut-offs that define which vertices participate in each Luby step; chosen large enough for Chernoff bounds to succeed but otherwise arbitrary constants.
  • tiling constant 40
    Number of angular tiles per layer that guarantees non-adjacency of every 40-th tile; a convenient integer larger than the geometric constant 2π arising from the hyperbolic distance formula.
assumptions (4)
  • domain assumption Poisson point process representation of threshold HRGs with intensity n·ρ(r, heta) and connection radius R=2 log n+C
    Standard generative model used throughout the HRG literature (Section 4); all probabilistic statements are with respect to this measure.
  • standard math Chernoff and Poisson-Chernoff tail bounds (Lemmas 42–43)
    Classical concentration inequalities invoked for every high-probability claim.
  • domain assumption Round-elimination sequences of length Θ(d) with label complexity O(d) for MIS and constant for MM on regular trees (Balliu et al., Brandt–Olivetti)
    Imported lower-bound technology; the paper only verifies that the sequences remain valid under the error probability induced by the HRG-to-tree coupling.
  • domain assumption Existence of a unique giant component of linear size and the absence of vertices too close to the origin a.a.s.
    Standard structural facts for HRGs with α∈(1/2,1) (Bode–Fountoulakis–Müller, Kiwi–Mitsche).
invented entities (2)
  • nice sector / box construction for d-ary trees
    purpose: Explicit geometric regions that force an induced regular tree of prescribed degree and height to appear with probability n^{-o(1)}
    Defined in Definition 19 and Algorithm 1; the only new combinatorial object needed for the lower bound.
  • angular separator pattern realised by two Luby steps
    purpose: Constant-round geometric shattering that reduces residual components to polylog size
    Core of the upper-bound algorithms (Section 5); fully analysed inside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed Symmetry Breaking on Hyperbolic Random Graphs." pith.science (2026). https://pith.science/paper/HTG3GSAM

@misc{pith2026260709170,
  author       = {Pith},
  title        = {Pith review of: Distributed Symmetry Breaking on Hyperbolic Random Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HTG3GSAM}},
  note         = {Machine review of arXiv:2607.09170}
}
abstract

Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative model of hyperbolic random graphs (HRGs), which provides a theoretical framework for studying such networks. Motivated by the observation that several algorithms perform better on real-world networks than their worst-case guarantees suggest, we design and analyse distributed algorithms under the assumption that the input graph is an HRG. Indeed, prior work has shown that the classical symmetry-breaking problem of $\Delta+1$ colouring, where $\Delta$ is the maximum degree of the graph, can be solved in 2 rounds on HRGs [Maus and Ruff; SODA'26]. In stark contrast to this 2-round algorithm for $\Delta+1$ colouring, we prove that the related symmetry-breaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: we establish a lower bound of $\Omega\left(\frac{\log\log n}{\log\log\log n}\right)$ for MIS and MM on HRGs. Our lower bound techniques rely on new structural insights that may be of independent interest: we show that HRGs contain $d$-ary trees with large height and degree which enables us to adapt and lift prior impossibility results for distributed algorithms to the setting of HRGs. We also show that these lower bounds are polynomial tight: we design algorithms tailored to HRGs that solve MIS and MM in $\tilde{\mathcal{O}}(\log^{5/3}\log n)$ rounds with high probability in the LOCAL model, improving over the general worst-case lower bound of $\Omega\left(\min\left\{\log \Delta, \sqrt{\log n}\right\}\right)$ rounds [Khoury and Schild; FOCS'25].

Figures

Figures reproduced from arXiv: 2607.09170 by the authors.

Figure 1
Figure 1. Landscape of randomised LOCAL Maximal Independent Set (MIS) and Maximal Matching (MM). Green: our results for MIS/MM on hyperbolic random graphs. Black: current state of the art for MIS/MM on general graphs. Grey: distributed colouring on HRGs. Disks: upper bounds (Theorem 1). Squares: lower bounds (Theorem 2). Triangles: embedding-aware upper bounds (Theorem 3). 1.1 Our Contributions We show that the complexity lan… view at source ↗
Figure 2
Figure 2. Shattering: (a) Vertices in the blue and red annuli are active in steps 1 and 2, respectively. (b) The [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Excerpt of a hyperbolic disk with trees. (a) Sketch of a nice sector (blue) with angle [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Sketch for our tiling. (a) Any pair of points in two different red tiles has a distance larger than [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: (a) Illustration of the neighbourhood 𝑁(𝑢) of a vertex 𝑢 given by 𝑉 ∩𝑢(𝑅) (blue region) following the geometry of the hyperbolic disk. The red area is the ball 0(𝑟) centred around the origin for some 𝑟. (b) Sketch of layer 0 (red area), layer 1 (yellow area) and so…
Figure 6
Figure 6. Figure 6: (a) Sketch of Lemma 10. All active vertices that join the independent set after the first step are [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: (a) The hatched area is removed after the second step of HRG-Shattering-MIS (Lemma 12). Case 1: [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: Sketch of our tree construction with degree [PITH_FULL_IMAGE:figures/full_fig_p026_8.png]
Figure 9
Figure 9. Figure 9: (a) Illustration of unmatched vertices in two annuli (blue and yellow area) and the set of edges [PITH_FULL_IMAGE:figures/full_fig_p044_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

90 extracted references · 36 canonical work pages

  1. [1]

    Typical distances in a geo- metric model for complex networks

    Mohammed Amin Abdullah, Nikolaos Fountoulakis, and Michel Bode. “Typical distances in a geo- metric model for complex networks”. In:Internet Math.(2017).doi:10.24166/IM.13.2017

    work page doi:10.24166/im.13.2017 2017

  2. [2]

    A fast and simple randomized parallel algorithm for the maximal independent set problem

    Noga Alon, László Babai, and Alon Itai. “A fast and simple randomized parallel algorithm for the maximal independent set problem”. In:Journal of Algorithms(1986).doi: 10.1016/0196-6774(86) 90019-2.url:http://dx.doi.org/10.1016/0196-6774(86)90019-2

    doi:10.1016/0196-6774(86 1986

  3. [3]

    Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring

    Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas. “Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring”. In:STACS’25. 2025.doi:10.4230/ LIPICS.STACS.2025.13

    2025

  4. [4]

    Distributed Quantum Advantage for Local Problems

    Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. “Distributed Quantum Advantage for Local Problems”. In:STOC’25. 2025

    2025

  5. [5]

    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”. In:J. ACM(2021).doi: 10.1145/3461458.url:https://doi.org/10.1145/3461458

    work page doi:10.1145/3461458.url:https://doi.org/10.1145/3461458 2021

  6. [6]

    DistributedΔ-coloring plays hide-and-seek

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “DistributedΔ-coloring plays hide-and-seek”. In:STOC’22. 2022.doi: 10.1145/3519935.3520027.url: https://doi.org/ 10.1145/3519935.3520027

    doi:10.1145/3519935.3520027.url: 2022

  7. [7]

    New Hardness Results for the LOCAL Model via a Simple Self-Reduction

    Alkida Balliu, Filippo Casagrande, Francesco d’Amore, and Dennis Olivetti. “New Hardness Results for the LOCAL Model via a Simple Self-Reduction”. In:PODC’26(2026).doi: 10.48550/ARXIV. 2510.19972

    doi:10.48550/arxiv 2026

  8. [8]

    Distributed Quantum Advantage in Locally Checkable Labeling Problems

    Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Massimo Equi, Barbara Keller, Henrik Lievo- nen, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. “Distributed Quantum Advantage in Locally Checkable Labeling Problems”. In:SODA’26.doi: 10.1137/1.9781611978971.49.url: https://epubs.siam.org/doi/abs/10.1137/1.9781611978971.49

    work page doi:10.1137/1.9781611978971.49.url:

Show all 90 references
  1. [9]

    Node and edge averaged complex- ities of local graph problems

    Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. “Node and edge averaged complex- ities of local graph problems”. In:Distributed Comput.(2023).doi: 10.1007/S00446-023-00453-1 . url:https://doi.org/10.1007/s00446-023-00453-1. 44

    2023 doi

  2. [10]

    Emergence of Scaling in Random Networks

    Albert-László Barabási and Réka Albert. “Emergence of Scaling in Random Networks”. In:Science (1999).doi:10.1126/science.286.5439.509

    1999 doi

  3. [11]

    Morgan & Claypool Publishers, 2013

    Leonid Barenboim and Michael Elkin.Distributed Graph Coloring: Fundamentals and Recent Develop- ments. Morgan & Claypool Publishers, 2013

    2013

  4. [13]

    The Locality of Distributed Symmetry Breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. “The Locality of Distributed Symmetry Breaking”. In:Journal of the ACM (JACM)(2016).doi:10.1145/2903137

    2016 doi

  5. [14]

    The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs

    Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi. “The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs”. In:STACS’26. 2026

    2026

  6. [15]

    Localized geometry detection in scale-free random graphs

    Gianmarco Bet, Riccardo Michielan, and Clara Stegehuis. “Localized geometry detection in scale-free random graphs”. In:Journal of Applied Probability(2025).doi:10.1017/jpr.2025.10038

    2025 doi

  7. [16]

    Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs

    Thomas Bläsius, Emil Dohse, Deborah Haun, and Laura Merker. “Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs”. In:SoCG’26. 2026.doi: 10.4230/LIPICS.SOCG.2026.18. url:https://doi.org/10.4230/LIPIcs.SoCG.2026.18

    2026 doi

  8. [17]

    On the External Validity of Average-case Analyses of Graph Algorithms

    Thomas Bläsius and Philipp Fischbeck. “On the External Validity of Average-case Analyses of Graph Algorithms”. In:ACM Transactions on Algorithms (TALG)(2024).doi:10.1145/3633778

    2024 doi

  9. [18]

    Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

    Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann. “Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs”. In:Theory Comput. Syst.(2023)

    2023

  10. [19]

    Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

    Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry. “Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry”. In:ACM Transactions on Algorithms (TALG)(2022).doi:10.1145/3516483

    2022 doi

  11. [20]

    Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry

    Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. “Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry”. In:Algorithmica(2023)

    2023

  12. [21]

    Efficiently generating geometric inhomogeneous and hyperbolic random graphs

    Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. “Efficiently generating geometric inhomogeneous and hyperbolic random graphs”. In:Network Science(2022).doi:10.1017/nws.2022.32

    2022 doi

  13. [22]

    On the Giant Component of Geometric Inhomogeneous Random Graphs

    Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, and Ziena Zeif. “On the Giant Component of Geometric Inhomogeneous Random Graphs”. In:ESA’23. 2023.doi: 10.4230/ LIPICS.ESA.2023.20

    2023

  14. [23]

    Strongly Hyperbolic Unit Disk Graphs

    Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. “Strongly Hyperbolic Unit Disk Graphs”. In:STACS’23. 2023.doi:10.4230/LIPIcs.STACS.2023.13

    2023 doi

  15. [24]

    Cliques in Hyperbolic Random Graphs

    Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. “Cliques in Hyperbolic Random Graphs”. In: Algorithmica(2018).doi:10.1007/s00453-017-0323-3

    2018 doi

  16. [25]

    Hyperbolic Random Graphs: Separators and Treewidth

    Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. “Hyperbolic Random Graphs: Separators and Treewidth”. In:ESA. 2016.doi:10.4230/LIPIcs.ESA.2016.15

    2016 doi

  17. [26]

    Structure and Independence in Hyperbolic Uniform Disk Graphs

    Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen. “Structure and Independence in Hyperbolic Uniform Disk Graphs”. In:SoCG’25. 2025. doi: 10.4230/LIPICS.SOCG.2025.21 .url: https://doi.org/10.4230/LIPIcs.SoCG. 2025.21

    2025 doi

  18. [27]

    Maximal cliques in scale-free random graphs

    Thomas Bläsius, Maximilian Katzmann, and Clara Stegehuis. “Maximal cliques in scale-free random graphs”. In:Network Science(2024).doi:10.1017/nws.2024.13. 45

    2024 doi

  19. [28]

    On the largest component of a hyperbolic model of complex networks

    Michel Bode, N. Fountoulakis, and Tobias Müller. “On the largest component of a hyperbolic model of complex networks”. In:Electronic Journal of Combinatorics(2015).doi:10.1214/17-AAP1314

    2015 doi

  20. [29]

    Sustaining the Internet with hyperbolic mapping

    Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. “Sustaining the Internet with hyperbolic mapping”. In:Nature Communications(2010).doi:10.1038/ncomms1063

    2010 doi

  21. [30]

    Truly Tight-in-ΔBounds for Bipartite Maximal Matching and Variants

    Sebastian Brandt and Dennis Olivetti. “Truly Tight-in-ΔBounds for Bipartite Maximal Matching and Variants”. In:PODC’20. 2020.doi: 10.1145/3382734.3405745.url: https://doi.org/10. 1145/3382734.3405745

    2020 doi

  22. [31]

    Geometric inhomogeneous random graphs

    Karl Bringmann, Ralph Keusch, and Johannes Lengler. “Geometric inhomogeneous random graphs”. In:Theoretical Computer Science(2019).doi: 10.1016/j.tcs.2018.08.014 .url: http://dx. doi.org/10.1016/j.tcs.2018.08.014

    2019 doi

  23. [32]

    Greedy routing and the algorithmic small-world phenomenon

    Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, and Anisur R. Molla. “Greedy routing and the algorithmic small-world phenomenon”. In:Journal of Computer and System Sciences (2022).doi: https : / / doi . org / 10 . 1016 / j . jcss . 2021 . 11 . 003.url: https : / /...

    2022

  24. [33]

    Balanced Bidirectional Breadth-First Search on Scale-Free Networks

    Sacha Cerf, Benjamin Dayan, Umberto De Ambroggio, Marc Kaufmann, Johannes Lengler, and Ulysse Schaller. “Balanced Bidirectional Breadth-First Search on Scale-Free Networks”. In:arXiv(2024).doi: 10.48550/ARXIV.2410.22186.url:https://arxiv.org/abs/2410.22186

    2024 doi arXiv

  25. [34]

    An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

    Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. “An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model”. In:SIAM J. Comput.(2019).doi: 10.1137/ 17M1117537.url:https://doi.org/10.1137/17M1117537

    2019 doi

  26. [35]

    An optimal distributed (Δ+1)-coloring algorithm?

    Yi-Jun Chang, Wenzheng Li, and Seth Pettie. “An optimal distributed (Δ+1)-coloring algorithm?” In: STOC’18. 2018

    2018

  27. [36]

    Connected Components in Random Graphs with Given Expected Degree Sequences

    Fan Chung and Linyuan Lu. “Connected Components in Random Graphs with Given Expected Degree Sequences”. In:Annals of Combinatorics(2002).doi:10.1007/PL00012580

    2002 doi

  28. [37]

    The Average Distances in Random Graphs with Given Expected Degrees

    Fan Chung and Linyuan Lu. “The Average Distances in Random Graphs with Given Expected Degrees”. In:Proceedings of the National Academy of Sciences(2002).doi:10.1073/pnas.252631999

    2002 doi

  29. [38]

    A Breezing Proof of the KMW Bound

    Corinna Coupette and Christoph Lenzen. “A Breezing Proof of the KMW Bound”. In:SOSA’21. 2021.doi: 10 . 1137 / 1 . 9781611976496 . 21.url: http : / / dx . doi . org / 10 . 1137 / 1 . 9781611976496.21

    2021

  30. [39]

    On power-law relationships of the internet topology

    Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. “On power-law relationships of the internet topology”. In:ACM SIGCOMM computer communication review(1999)

    1999

  31. [40]

    Local Dis- tributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

    Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and Václav Rozhon. “Local Dis- tributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond”. In:SODA’23. 2023.doi: 10.1137/1.9781611977554.CH168 .url: https://doi.org/10.1137/1.9781611977554. ch168

    2023 doi

  32. [41]

    Improved deterministic distributed matching via rounding

    Manuela Fischer. “Improved deterministic distributed matching via rounding”. In:Distributed Com- puting(2020)

    2020

  33. [42]

    Law of large numbers for the largest component in a hyperbolic model of complex networks

    Nikolaos Fountoulakis and Tobias Müller. “Law of large numbers for the largest component in a hyperbolic model of complex networks”. In:The Annals of Applied Probability(2018).url: https: //www.jstor.org/stable/26542317

    2018

  34. [43]

    On the Diameter of Hyperbolic Random Graphs

    Tobias Friedrich and Anton Krohmer. “On the Diameter of Hyperbolic Random Graphs”. In:SIAM Journal on Discrete Mathematics(2018).doi:10.1137/17M1123961. 46

    2018 doi

  35. [44]

    An Improved Distributed Algorithm for Maximal Independent Set

    Mohsen Ghaffari. “An Improved Distributed Algorithm for Maximal Independent Set”. In:SODA’16. 2016.doi: 10 . 1137 / 1 . 9781611974331 . CH20.url: https : / / doi . org / 10 . 1137 / 1 . 9781611974331.ch20

    2016

  36. [45]

    Distributed Maximal Independent Set using Small Messages

    Mohsen Ghaffari. “Distributed Maximal Independent Set using Small Messages”. In:SODA’19. 2019. doi: 10.1137/1.9781611975482.50.url: https://doi.org/10.1137/1.9781611975482. 50

    2019 doi

  37. [46]

    Faster deterministic distributed MIS and approximate matching

    Mohsen Ghaffari and Christoph Grunau. “Faster deterministic distributed MIS and approximate matching”. In:STOC’23. 2023

    2023

  38. [47]

    Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS

    Mohsen Ghaffari and Christoph Grunau. “Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS”. In:FOCS’24. 2024.doi:10.1109/FOCS61266.2024.00007

    2024 doi

  39. [48]

    Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization

    Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. “Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization”. In:SODA’23. 2023.doi: 10.1137/1.9781611977554.ch97.url: https://epubs.siam.org/doi/abs/10. 1137/...

    2023 doi

  40. [49]

    Halldórsson, Yannic Maus, and Alexandre Nolin.Robust Shattering Arguments

    Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin.Robust Shattering Arguments. 2026. arXiv:2606.27847.url:https://arxiv.org/abs/2606.27847

    2026 arXiv

  41. [50]

    Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond

    Mohsen Ghaffari and Julian Portmann. “Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond”. In:DISC’19. 2019.doi: 10.4230/ LIPIcs . DISC . 2019 . 18.url: https : / / drops . dagstuhl . de / entities / document / 10 . 4...

    2019

  42. [51]

    Random Hyperbolic Graphs: Degree Sequence and Clustering

    Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. “Random Hyperbolic Graphs: Degree Sequence and Clustering”. In:ICALP’12. 2012.doi:10.1007/978-3-642-31585-5_51

    2012 doi

  43. [52]

    Distributed (Δ+1)-Coloring in Sublogarith- mic Rounds

    David G. Harris, Johannes Schneider, and Hsin-Hao Su. “Distributed (Δ+1)-Coloring in Sublogarith- mic Rounds”. In:J. ACM(2018).url:https://doi.org/10.1145/3178120

    2018 doi

  44. [53]

    Cluster-size decay in supercritical kernel-based spatial random graphs

    Joost Jorritsma, Júlia Komjáthy, and Dieter Mitsche. “Cluster-size decay in supercritical kernel-based spatial random graphs”. In:The Annals of Probability(2025).doi: 10 . 1214 / 24 - aop1742.url: http://dx.doi.org/10.1214/24-AOP1742

    2025 doi

  45. [54]

    About the analysis of algorithms on networks with underlying hyperbolic geometry

    Maximilian Katzmann. “About the analysis of algorithms on networks with underlying hyperbolic geometry”. PhD thesis. Universität Potsdam, 2023.doi: 10 . 25932 / PUBLISHUP - 58296.url: https://publishup.uni-potsdam.de/58296

    2023

  46. [55]

    Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models

    Marc Kaufmann, Kostas Lakis, Johannes Lengler, Raghu Raman Ravi, Ulysse Schaller, and Konstantin Sturm. “Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models”. In:SODA’26. 2026.doi: 10.1137/1.9781611978971.226.url: https://doi. org/1...

    2026 doi

  47. [56]

    Breaking Barriers for Distributed MIS by Faster Degree Reduction

    Seri Khoury and Aaron Schild. “Breaking Barriers for Distributed MIS by Faster Degree Reduction”. In:STOC’26(2026).doi: 10 . 1145 / 3798129 . 3800816.url: https : / / doi . org / 10 . 1145 / 3798129.3800816

    2026

  48. [57]

    Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching

    Seri Khoury and Aaron Schild. “Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching”. In:FOCS’25(2025).doi: 10.1109/FOCS63196.2025.00120 .url: https: //doi.org/10.1109/FOCS63196.2025.00120

    2025 doi

  49. [58]

    Hyperbolic intersection graphs and (quasi)-polynomial time

    Sándor Kisfaludi-Bak. “Hyperbolic intersection graphs and (quasi)-polynomial time”. In:SODA’20. 2020.doi: 10 . 1137 / 1 . 9781611975994 . 100 .url: https : / / doi . org / 10 . 1137 / 1 . 9781611975994.100. 47

    2020

  50. [59]

    A Bound for the Diameter of Random Hyperbolic Graphs

    Marcos Kiwi and Dieter Mitsche. “A Bound for the Diameter of Random Hyperbolic Graphs”. In: ANALCO’15. 2015.doi:10.1137/1.9781611973761.3

    2015 doi

  51. [60]

    On the Second Largest Component of Random Hyperbolic Graphs

    Marcos Kiwi and Dieter Mitsche. “On the Second Largest Component of Random Hyperbolic Graphs”. In:SIAM Journal on Discrete Mathematics(2019).doi:10.1137/18M121201X

    2019 doi

  52. [61]

    Spectral gap of random hyperbolic graphs and related parameters

    Marcos Kiwi and Dieter Mitsche. “Spectral gap of random hyperbolic graphs and related parameters”. In:The Annals of Applied Probability(2018).doi:10.1214/17-aap1323

    2018 doi

  53. [62]

    Cover and hitting times of hyperbolic random graphs

    Marcos Kiwi, Markus Schepers, and John Sylvester. “Cover and hitting times of hyperbolic random graphs”. In:Random Structures & Algorithms(2024).doi:10.1002/rsa.21249

    2024 doi

  54. [63]

    Polynomial growth in degree- dependent first passage percolation on spatial random graphs

    Júlia Komjáthy, John Lapinskas, Johannes Lengler, and Ulysse Schaller. “Polynomial growth in degree- dependent first passage percolation on spatial random graphs”. In:Electronic Journal of Probability (2024).doi:10.1214/24-ejp1216.url:http://dx.doi.org/10.1214/24-EJP1216

    2024 doi

  55. [64]

    Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs

    Júlia Komjáthy and Bas Lodewijks. “Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs”. In:Stochastic Processes and their Applications(2020).doi: 10.1016/ j.spa.2019.04.014.url:http://dx.doi.org/10.1016/j.spa.2019.04.014

    2020 doi

  56. [65]

    Koonin, Yuri I

    Eugene V. Koonin, Yuri I. Wolf, and Georgy P. Karev.Power Laws, Scale-Free Networks and Genome Biology. Springer US, 2006.doi: 10.1007/0- 387- 33916- 7 .url: http://dx.doi.org/10. 1007/0-387-33916-7

    2006 doi

  57. [66]

    Hyperbolic Geometry of Complex Networks

    Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. “Hyperbolic Geometry of Complex Networks”. In:Physical Review E(2010).doi: 10.1103/PhysRevE. 82.036106

    2010 doi

  58. [67]

    Structures & algorithms in hyperbolic random graphs

    Anton Krohmer. “Structures & algorithms in hyperbolic random graphs”. doctoralthesis. Universität Potsdam, 2016.url: https : / / publishup . uni - potsdam . de / frontdoor / index / index / docId/39597

    2016

  59. [68]

    Fast Deterministic Dis- tributed Maximal Independent Set Computation on Growth-Bounded Graphs

    Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer. “Fast Deterministic Dis- tributed Maximal Independent Set Computation on Growth-Bounded Graphs”. In:DISC’05. 2005.url: https://www.microsoft.com/en- us/research/publication/fast- deterministic- distributed-max...

    2005

  60. [69]

    Local Computation: Lower and Upper Bounds

    Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. “Local Computation: Lower and Upper Bounds”. In:J. ACM(2016).doi: 10.1145/2742012.url: https://doi.org/10.1145/2742012

    2016 doi

  61. [70]

    MIS on trees

    Christoph Lenzen and Roger Wattenhofer. “MIS on trees”. In:PODC’11. 2011

    2011

  62. [71]

    Distributive graph algorithms Global solutions from local data

    Nathan Linial. “Distributive graph algorithms Global solutions from local data”. In:FOCS’87. 1987. doi:10.1109/SFCS.1987.20

    1987 doi

  63. [72]

    Locality in Distributed Graph Algorithms

    Nathan Linial. “Locality in Distributed Graph Algorithms”. In:SIAM Journal on Computing(1992). doi:10.1137/0221015

    1992 doi

  64. [73]

    A Simple Parallel Algorithm for the Maximal Independent Set Problem

    M. Luby. “A Simple Parallel Algorithm for the Maximal Independent Set Problem”. In:SIAM Journal on Computing(1986)

    1986

  65. [74]

    On Distributed Colouring of Hyperbolic Random Graphs

    Yannic Maus and Janosch Ruff. “On Distributed Colouring of Hyperbolic Random Graphs”. In: SODA’26. 2026.doi: 10.1137/1.9781611978971.91 .url: https://doi.org/10.1137/1. 9781611978971.91

    2026 doi

  66. [75]

    An optimal bit complexity randomized distributed MIS algorithm

    Y. Métivier, J. M. Robson, N. Saheb-Djahromi, and A. Zemmari. “An optimal bit complexity randomized distributed MIS algorithm”. In:Distributed Computing(2010).doi: 10.1007/s00446-010-0121-5 . url:http://dx.doi.org/10.1007/s00446-010-0121-5. 48

    2010 doi

  67. [76]

    Cliques in geometric inhomogeneous random graphs

    Riccardo Michielan and Clara Stegehuis. “Cliques in geometric inhomogeneous random graphs”. In:J. Complex Networks(2021).doi: 10.1093/COMNET/CNAC002 .url: https://doi.org/10. 1093/comnet/cnac002

    2021 doi

  68. [77]

    Optimal deterministic distributed algorithms for maximal independent set in geometric graphs

    Anisur Rahaman Molla, Supantha Pandit, and Sasanka Roy. “Optimal deterministic distributed algorithms for maximal independent set in geometric graphs”. In:Journal of Parallel and Distributed Computing(2019).doi:10.1016/j.jpdc.2019.05.012

    2019 doi

  69. [78]

    The Diameter of KPKVB Random Graphs

    Tobias Müller and Merlijn Staps. “The Diameter of KPKVB Random Graphs”. In:Advances in Applied Probability(2019).doi:10.1017/apr.2019.23

    2019 doi

  70. [79]

    A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring

    M. Naor. “A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring”. In:SIAM J. Discrete Math.(1991)

    1991

  71. [80]

    Why social networks are different from other types of networks

    M. E. J. Newman and Juyong Park. “Why social networks are different from other types of networks”. In:Phys. Rev. E(2003).doi:10.1103/physreve.68.036122

    2003 doi

  72. [81]

    Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces

    Fragkiskos Papadopoulos, Dmitri V. Krioukov, Marián Boguñá, and Amin Vahdat. “Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces”. In:INFOCOM’10. 2010. doi:10.1109/INFCOM.2010.5462131

    2010 doi

  73. [82]

    David Peleg.Distributed computing: a locality-sensitive approach. 2000

    2000

  74. [83]

    Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

    Sriram V. Pemmaraju and Talal Riaz. “Using Read-k Inequalities to Analyze a Distributed MIS Algorithm”. In:OPODIS’16. 2016.doi: 10.4230/LIPICS.OPODIS.2016.9 .url: https://doi. org/10.4230/LIPIcs.OPODIS.2016.9

    2016 doi

  75. [84]

    Oxford University Press, 2003.isbn: 9780198506263

    Mathew Penrose.Random Geometric Graphs. Oxford University Press, 2003.isbn: 9780198506263

    2003

  76. [85]

    Polylogarithmic-time deterministic network decomposition and distributed derandomization

    Václav Rozhoň and Mohsen Ghaffari. “Polylogarithmic-time deterministic network decomposition and distributed derandomization”. In:STOC’20. 2020

    2020

  77. [86]

    An optimal maximal independent set algorithm for bounded-independence graphs

    Johannes Schneider and Roger Wattenhofer. “An optimal maximal independent set algorithm for bounded-independence graphs”. In:Distributed Computing(2010).doi: 10.1007/s00446- 010- 0097-1.url:http://dx.doi.org/10.1007/s00446-010-0097-1

    2010 doi

  78. [87]

    Clustering in complex networks. I. General formalism

    M. Ángeles Serrano and Marián Boguñá. “Clustering in complex networks. I. General formalism”. In: Phys. Rev. E(2006).doi:10.1103/PhysRevE.74.056114

    2006 doi

  79. [88]

    Self-Similarity of Complex Networks and Hidden Metric Spaces

    M. Ángeles Serrano, Dmitri Krioukov, and Marián Boguñá. “Self-Similarity of Complex Networks and Hidden Metric Spaces”. In:Physical Review Letters(2008).doi: 10.1103/physrevlett.100. 078701

    2008 doi

  80. [89]

    Scale-free Networks Well Done

    Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, and Dmitri Krioukov. “Scale-free Networks Well Done”. In:Physical Review Research(2019).doi:10.1103/PhysRevResearch.1.033034

    2019 doi

  81. [90]

    Collective dynamics of ‘small-world’ networks

    Duncan J. Watts and Steven H. Strogatz. “Collective dynamics of ‘small-world’ networks”. In:Nature (1998).doi:10.1038/30918. 49 A Luby’s Algorithm Retains a Polynomial Degree After Constant Rounds In this section, we show that a standard Luby algorithm requires more than const...

    1998 doi

  82. [91]

    remaining leaves

    Similar degree path of 𝑢: For any constant 𝑡∈(1),𝑢has a similar degree path 𝑊(𝑢)of length at least2𝑡. Moreover, for any pair𝑢,𝑢′∈𝑈(𝜀)it holds that for any pair𝑣∈𝐿(𝑢)∪𝑊(𝑢)∪{𝑢}and𝑣′∈𝐿(𝑢′)∪𝑊(𝑢′)∪{𝑢′} that{𝑣,𝑣′}∉𝐸(𝐺). Proof. We partition the disk 𝑅into ⌊ 𝑛⋅2𝜋 𝑛1/(2𝛼)+𝜀⌋=∶𝑘sector...

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.