Almost global problems in the LOCAL model

DOI10.4230/LIPICS.DISC.2018.9MaRDI QIDQ5090898zbMATH OpenOpenAlexFDO

Authors Alkida Balliu, Sebastian F. Brandt, Dennis Olivetti, Jukka Suomela

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.DISC.2018.9

zbMATH Keywords

distributed complexity theoryLOCAL modellocally checkable labellings

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Almost global problems in the LOCAL model
• New classes of distributed time complexity
• A time hierarchy theorem for the LOCAL model
• On the complexity of local distributed graph problems
• LCL problems on grids

Cites work

• A lower bound for the distributed Lovász local lemma
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Deterministic (+1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed Computing: A Locality-Sensitive Approach
• Distributed degree splitting, edge coloring, and orientations
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• On the Computational Complexity of Algorithms
• Some simple distributed algorithms for sparse networks
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• What Can be Computed Locally?

Cited in

(13)

• Almost global problems in the LOCAL model
• Distributed graph problems through an automata-theoretic lens
• Local collapses in the Truscott-Brindley model
• Local-on-average distributed tasks
• A time hierarchy theorem for the LOCAL model
• LCL problems on grids
• scientific article; zbMATH DE number 5242355 (Why is no real title available?)
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Message reduction in the LOCAL model is a free lunch
• Classification of distributed binary labeling problems
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Shared randomness in locally checkable problems: the role of computational assumptions

This page was built for publication: Almost global problems in the LOCAL model

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