Publisher Copyright: © 2026 Copyright held by the owner/author(s).

One of the most successful theoretical models in distributed computing is LOCAL, introduced in a seminal work by Linial [SIAM J. Comp. 1992]. Over the years, when studying distributed graph problems in the LOCAL model, researchers made different assumptions on the exact details of this model. For example, sometimes it is assumed that all machines know the exact size of the network, other times machines are assumed to only know a polynomial upper bound on the size of the network, while sometimes no prior knowledge is assumed. Are these small differences irrelevant details or do they actually heavily affect the obtained results? We investigate how robust our current understanding of the LOCAL model truly is, by focusing on one of the most studied classes of problems, called Locally Checkable Labelings (LCLs).

The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of research with regards to this new complexity measure is to understand the complexity landscape of locally checkable labelings (LCLs) on families of bounded-degree graphs. Particularly interesting in this context is the family of bounded-degree trees as there, for the worst-case complexity, we know a complete characterization of the possible complexities and structures of LCL problems. A first step for the node-averaged complexity case has been achieved recently [DISC '23], where the authors in particular showed that in bounded-degree trees, there is a large complexity gap: There are no LCL problems with a deterministic node-averaged complexity between ω(log* n) and no(1). For randomized algorithms, they even showed that the node-averaged complexity is either O(1) or nΩ(1). In this work we fill in the remaining gaps and give a complete description of the node-averaged complexity landscape of LCLs on bounded-degree trees. Our contributions are threefold.

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: