podc_camera_ready.pdf (689.5 kB)

# Completing the Node-Averaged Complexity Landscape of LCLs on Trees

conference contribution

posted on 2024-05-14, 09:18 authored by Alkida Balliu, Sebastian BrandtSebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav SchmidThe 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 n^{o(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 0 < r_1 < r_2 ≤ 1 and ε > 0, 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 Θ(n^x) for some x ∈ [α, α+ε].

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM Symposium on Principles of Distributed Computing (PODC)## BibTeX

@conference{Balliu:Brandt:Kuhn:Olivetti:Schmid:2024, title = "Completing the Node-Averaged Complexity Landscape of LCLs on Trees", author = "Balliu, Alkida" AND "Brandt, Sebastian" AND "Kuhn, Fabian" AND "Olivetti, Dennis" AND "Schmid, Gustav", year = 2024, month = 6 }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC