Journal article · 2026 · Open access

On the Node-Averaged Complexity of Locally Checkable Problems on Trees

Alkida Balliu, Sebastian Brandt, Fabian Kühn, Dennis Olivetti, Gustav Schmid

Journal of the ACM, 73(4), 1–67 · Published 12 June 2026 · DOI 10.1145/3820037

Open full textCite this paper

In brief

“On the Node-Averaged Complexity of Locally Checkable Problems on Trees” is a 2026 journal article by Alkida Balliu and 4 co-authors, published in Journal of the ACM. OpenAlex counts 5 citations as of 17 November 2026. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.

Citations
5
Most cited in
2025 (2)
Field-weighted impact
3.32
References
34
Authors
5

Abstract

Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminating in an almost-complete classification on general graphs and a complete classification on trees. The latter states that, on bounded-degree trees, any LCL problem has deterministic worst-case time complexity O (1), Θ (log * n), Θ (log n ), or Θ ( n 1/ k ) for some positive integer k , and all of those complexity classes are nonempty. Moreover, randomness helps only for (some) problems with deterministic worst-case complexity Θ (log n ), and if randomness helps (asymptotically), then it helps exponentially. In this work, we study how many distributed rounds are needed on average per node in order to solve an LCL problem on trees. We obtain a partial classification of the deterministic node-averaged complexity landscape for LCL problems. As our main result, we show that every problem with worst-case round complexity O (log n ) has deterministic node-averaged complexity O (log * n ). Then we show how using randomization we can speed this up and show that every problem with worst case round complexity O (log n ) has randomized node-averaged complexity O (1). We further establish bounds on the node-averaged complexity of problems with worst-case complexity Θ ( n 1/ k ): we show that all these problems have node-averaged complexity \(\widetilde{\Omega }(n^{1 / (2^k - 1)})\) , and that this lower bound is tight for some problems. The lower bound holds even for the randomized case and the upper bound is a deterministic algorithm.

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., Kühn, F., Olivetti, D., & Schmid, G. (2026). On the Node-Averaged Complexity of Locally Checkable Problems on Trees. Journal of the ACM, 73(4), 1–67. https://doi.org/10.1145/3820037

MLA 9

Balliu, Alkida, et al. “On the Node-Averaged Complexity of Locally Checkable Problems on Trees.” Journal of the ACM, vol. 73, no. 4, 2026, pp. 1–67. https://doi.org/10.1145/3820037.

Chicago

Balliu, Alkida, Sebastian Brandt, Fabian Kühn, Dennis Olivetti, and Gustav Schmid. 2026. “On the Node-Averaged Complexity of Locally Checkable Problems on Trees.” Journal of the ACM 73 (4): 1–67. https://doi.org/10.1145/3820037.

Harvard

Balliu, A. et al. (2026) ‘On the Node-Averaged Complexity of Locally Checkable Problems on Trees’, Journal of the ACM, 73(4), pp. 1–67. doi:10.1145/3820037.

IEEE

A. Balliu, S. Brandt, F. Kühn, D. Olivetti, and G. Schmid, “On the Node-Averaged Complexity of Locally Checkable Problems on Trees,” Journal of the ACM, vol. 73, no. 4, pp. 1–67, 2026, doi: 10.1145/3820037.

BibTeX

@article{balliu2026node,
  title     = {{On the Node-Averaged Complexity of Locally Checkable Problems on Trees}},
  author    = {Balliu, Alkida and Brandt, Sebastian and Kühn, Fabian and Olivetti, Dennis and Schmid, Gustav},
  journal   = {Journal of the ACM},
  year      = {2026},
  volume    = {73},
  number    = {4},
  pages     = {1--67},
  doi       = {10.1145/3820037},
  url       = {https://doi.org/10.1145/3820037}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202411
202522
202622

Its field-weighted citation impact is 3.32: it has been cited 3.32 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

  • trees
  • bounded degree graphs
  • randomized distributed algorithms
  • deterministic distributed algorithms
  • round complexity
  • lower bounds

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Balliu, A., Brandt, S., Kühn, F., Olivetti, D., & Schmid, G. (2026). On the Node-Averaged Complexity of Locally Checkable Problems on Trees. Journal of the ACM, 73(4), 1–67. https://doi.org/10.1145/3820037

How many times has this paper been cited?

5 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 Kühn, Dennis Olivetti, Gustav Schmid.

What is the DOI of this paper?

10.1145/3820037, permanently at https://doi.org/10.1145/3820037. 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.