Classification of distributed binary labeling problems

DOI10.4230/LIPICS.DISC.2020.17zbMATH Open1540.68164MaRDI QIDQ6535014FDOQ6535014

Authors: Alkida Balliu, Sebastian F. Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela 

Publication date: 2 November 2023

Recommendations

• Brief Announcement: Classification of Distributed Binary Labeling Problems
• New classes of distributed time complexity
• Almost global problems in the LOCAL model
• Almost global problems in the LOCAL model
• Graph labelings derived from models in distributed computing: A complete complexity classification

zbMATH Keywords

graph problemsLOCAL modeldistributed computational complexitylocally checkable labeling problems

Mathematics Subject Classification ID

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

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• Locality in Distributed Graph Algorithms
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Deterministic coin tossing with applications to optimal parallel list ranking
• What Can be Computed Locally?
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• A time hierarchy theorem for the LOCAL model
• Title not available (Why is that?)
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed degree splitting, edge coloring, and orientations
• On the complexity of local distributed graph 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?
• 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
• Improved distributed degree splitting and edge coloring
• Almost global problems in the LOCAL model
• A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
• Brief Announcement: Round eliminator: a tool for automatic speedup simulation

Cited In (2)

• Distributed Data Structures: A Survey on Informative Labeling Schemes
• An efficient distributed algorithm for canonical labeling on directed split-stars

This page was built for publication: Classification of distributed binary labeling problems

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