The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, Gustav Schmid · 2026
Read The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size by Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, Gustav Schmid (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12787.txt.
Introduction
Balliu and five colleagues ask whether small changes in what network nodes know about network size matter for distributed computing theory. They study locally checkable labellings, problems whose solutions can be verified from small neighbourhoods. When nodes know nothing about size, or only a rough upper bound, the theory shifts. Randomness helps in more cases, some problems gain odd complexities, and some lower bounds hinge on the exact definition used.
Catalog record
| CREATOR | Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, Gustav Schmid |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 187140 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.12787