Journal article · 2026 · Open access
Distributed Δ-Coloring Plays Hide-and-Seek
Journal of the ACM, 73(4), 1–58 · Published 16 June 2026 · DOI 10.1145/3819817
In brief
“Distributed Δ-Coloring Plays Hide-and-Seek” is a 2026 journal article by Alkida Balliu and 3 co-authors, published in Journal of the ACM. OpenAlex counts 8 citations as of 17 November 2026, which puts it in the top 7% of works published in 2026 by citations. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.
- Citations
- 8
- Most cited in
- 2022 (3)
- Field-weighted impact
- 7.12
- References
- 63
- Authors
- 4
Abstract
We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a Δ-coloring on Δ-regular trees requires Ω (log Δ n ) rounds and any randomized such algorithm requires Ω (log Δ log n ) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework. As a first application, we show that our Δ-coloring lower bound proof directly extends to arbdefective colorings. An arbdefective c -coloring of a graph G=(V,E) is given by a c -coloring of V and an orientation of E , where the arbdefect of a color i is the maximum number of monochromatic outgoing edges of any node of color i . We exactly characterize which variants of the arbdefective coloring problem can be solved in O ( f (Δ) + log * n ) rounds, for some function f , and which of them instead require Ω (log Δ n ) rounds for deterministic algorithms and Ω (log Δ log n ) rounds for randomized ones. As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of Δ for problems that, in some sense, are much easier than Δ-coloring, as they can be solved in O (log * n ) deterministic rounds in bounded-degree graphs. More specifically, we prove lower bounds as a function of Δ for a large class of distributed symmetry breaking problems, which can all be solved by a simple sequential greedy algorithm. For example, we obtain novel results for the fundamental problem of computing a (2,β)-ruling set, i.e., for computing an independent set S ⊆ V such that every node v ∈ V is within distance ≤ β of some node in S . We in particular show that Ω (β Δ 1/β ) rounds are needed even if initially an O (Δ)-coloring of the graph is given. With an initial O (Δ)-coloring, this lower bound is tight and without, it still nearly matches the existing O (β Δ 2/(β +1) +log * n ) upper bound. The new (2,β)-ruling set lower bound is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS ’20]. As a special case of the lower bound, we also obtain a…
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Balliu, A., Brandt, S., Kuhn, F., & Olivetti, D. (2026). Distributed Δ-Coloring Plays Hide-and-Seek. Journal of the ACM, 73(4), 1–58. https://doi.org/10.1145/3819817
MLA 9
Balliu, Alkida, et al. “Distributed Δ-Coloring Plays Hide-and-Seek.” Journal of the ACM, vol. 73, no. 4, 2026, pp. 1–58. https://doi.org/10.1145/3819817.
Chicago
Balliu, Alkida, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2026. “Distributed Δ-Coloring Plays Hide-and-Seek.” Journal of the ACM 73 (4): 1–58. https://doi.org/10.1145/3819817.
Harvard
Balliu, A. et al. (2026) ‘Distributed Δ-Coloring Plays Hide-and-Seek’, Journal of the ACM, 73(4), pp. 1–58. doi:10.1145/3819817.
IEEE
A. Balliu, S. Brandt, F. Kuhn, and D. Olivetti, “Distributed Δ-Coloring Plays Hide-and-Seek,” Journal of the ACM, vol. 73, no. 4, pp. 1–58, 2026, doi: 10.1145/3819817.
BibTeX
@article{balliu2026distributed,
title = {{Distributed Δ-Coloring Plays Hide-and-Seek}},
author = {Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {4},
pages = {1--58},
doi = {10.1145/3819817},
url = {https://doi.org/10.1145/3819817}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2022 | 3 | |
| 2023 | 2 | |
| 2026 | 3 |
Its field-weighted citation impact is 7.12: it has been cited 7.12 times as often as the average work of the same field, type and year (1.00 is the world average).
Topic and keywords
Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- distributed graph algorithms
- symmetry breaking
- maximal independent sets
- maximal matching
- greedy algorithm
- randomized algorithms
- deterministic algorithms
- bounded degree graphs
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Balliu, A., Brandt, S., Kuhn, F., & Olivetti, D. (2026). Distributed Δ-Coloring Plays Hide-and-Seek. Journal of the ACM, 73(4), 1–58. https://doi.org/10.1145/3819817
How many times has this paper been cited?
8 times, according to OpenAlex on 17 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at Journal of the ACM: sign in and open the full text from this page.
Who wrote this paper?
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti.
What is the DOI of this paper?
10.1145/3819817, permanently at https://doi.org/10.1145/3819817. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 17 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.