2024/05/02 by Alkida Balliu, Balliu, Alkida, Sebastian Brandt +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Database Systems and Queries #DNA and Biological Computing #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2405.01366
openalex publication_date 2024/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. - On bounded-degree trees, there is no LCL with a node-averaged complexity between ω(1) and (log^*n)o(1). - For any constants 00, there exists a constant c and an LCL problem with node-averaged complexity between Ω((log^* n)c) and O((log^* n)c+ε). - For any constants 0<α≤ 1/2 and ε>0, there exists an LCL problem with node-averaged complexity Θ(nx) for some x∈ [α, α+ε].