The complexity landscape of distributed locally checkable problems on trees
From MaRDI portal
Publication:6535015
DOI10.4230/LIPICS.DISC.2020.18zbMATH Open1540.68302MaRDI QIDQ6535015FDOQ6535015
Authors: Yi-Jun Chang 
Publication date: 2 November 2023
Recommendations
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- On the complexity of local distributed graph problems
- Towards a complexity theory for local distributed computing
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
- Randomized Lower Bound for Distributed Spanning-Tree Verification
- A new approach on locally checkable problems
- Locally checkable proofs in distributed computing
- Average and Randomized Complexity of Distributed Problems
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)
Cites Work
- Distributed Computing: A Locality-Sensitive Approach
- Locality in Distributed Graph Algorithms
- Distributed edge coloring and a special case of the constructive Lovász local lemma
- What Can be Computed Locally?
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- A time hierarchy theorem for the LOCAL model
- Distributed algorithms for the Lovász local lemma and graph coloring
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- 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?
- Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
- An Automatic Speedup Theorem for Distributed Problems
- Brief Announcement: Classification of Distributed Binary Labeling Problems
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- Hardness of Minimal Symmetry Breaking in Distributed Computing
- Brief Announcement: Round eliminator: a tool for automatic speedup simulation
Cited In (1)
This page was built for publication: The complexity landscape of distributed locally checkable problems on trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535015)
