Completing the node-averaged complexity landscape of LCLs on trees

DOI10.1145/3662158.3662773MaRDI QIDQ6971930zbMATH OpenFDO

Authors Alkida Balliu, Sebastian F. Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid

Publication date 13 June 2025

Full work available at URL https://doi.org/10.1145/3662158.3662773

zbMATH Keywords

distributed complexity theorylocally checkable labelingsnode-averaged complexity

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites work

• A time hierarchy theorem for the LOCAL model
• Almost global problems in the LOCAL model
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Classification of distributed binary labeling problems
• Deterministic distributed vertex coloring: simpler, faster, and without network decomposition
• Distributed graph problems through an automata-theoretic Lens
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• How long it takes for an ordinary node with an ordinary ID to output?
• How much does randomness help with locally checkable problems?
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• Locally checkable labelings with small messages
• Locally checkable problems in rooted trees
• New classes of distributed time complexity
• Node and edge averaged complexities of local graph problems
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• The Landscape of Distributed Complexities on Trees and Beyond
• The complexity landscape of distributed locally checkable problems on trees
• What Can be Computed Locally?

This page was built for publication: Completing the node-averaged complexity landscape of LCLs on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6971930)