The complexity landscape of distributed locally checkable problems on trees

DOI10.4230/LIPICS.DISC.2020.18MaRDI QIDQ6535015zbMATH OpenFDO

Authors Yi-Jun Chang

Publication date 2 November 2023

zbMATH Keywords

distributed algorithmsLOCAL modellocally checkable labeling

Mathematics Subject Classification ID

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)

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

Cites work

• A lower bound for the distributed Lovász local lemma
• A time hierarchy theorem for the LOCAL model
• An Automatic Speedup Theorem for Distributed Problems
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Brief Announcement: Round eliminator: a tool for automatic speedup simulation
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• How much does randomness help with locally checkable problems?
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• New classes of distributed time complexity
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• What Can be Computed Locally?

Cited in

(1)

• Notes on the Distributed Computation of Merge Trees on CW-Complexes

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)