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

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2020.18

zbMATH Keywords

distributed algorithmsLOCAL modellocally checkable labeling

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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 algorithms for the Lovász local lemma and graph coloring
• Distributed Computing: A Locality-Sensitive Approach
• 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

(6)

• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• Notes on the Distributed Computation of Merge Trees on CW-Complexes
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
• Completing the node-averaged complexity landscape of LCLs on trees

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)