The complexity landscape of distributed locally checkable problems on trees
From MaRDI portal
Publication:6535015
DOI10.4230/lipics.disc.2020.18zbMath1540.68302MaRDI QIDQ6535015
Publication date: 2 November 2023
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
Cites Work
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- A Time Hierarchy Theorem for the LOCAL Model
- What Can be Computed Locally?
- Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- Hardness of Minimal Symmetry Breaking in Distributed Computing
- An Automatic Speedup Theorem for Distributed Problems
- New classes of distributed time complexity
- A lower bound for the distributed Lovász local lemma
- LCL Problems on Grids
- How much does randomness help with locally checkable problems?
- Brief Announcement: Classification of Distributed Binary Labeling Problems
- Brief Announcement: Round eliminator: a tool for automatic speedup simulation
- Distributed algorithms for the Lovász local lemma and graph coloring
- Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
This page was built for publication: The complexity landscape of distributed locally checkable problems on trees
