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

CREATORAlkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, Gustav Schmid
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE187140
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.12787

Browse the full library · About the Tower of Babel