An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

DOI10.1137/17M1117537zbMath1404.05203OpenAlexW2913663107WikidataQ115525618 ScholiaQ115525618MaRDI QIDQ4620411

Seth Pettie, Tsvi Kopelowitz, Yi-Jun Chang

Publication date: 8 February 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1117537

zbMATH Keywords

symmetry breakingcoloringdistributed algorithmlocal model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (14)

Locally checkable problems in rooted trees ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Component stability in low-space massively parallel computation ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Exact distributed sampling ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Distributed coloring of hypergraphs ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Almost global problems in the LOCAL model ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Distributed algorithms for fractional coloring ⋮ Distributed graph problems through an automata-theoretic Lens

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular graphs of large girth and arbitrary degree
• An optimal maximal independent set algorithm for bounded-independence graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Chromatic number, girth and maximal degree
• Distributed coloring algorithms for triangle-free graphs
• Proof labeling schemes
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Super-Fast 3-Ruling Sets.
• Local Computation
• The Locality of Distributed Symmetry Breaking
• Impossibility of distributed consensus with one faulty process
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed Degree Splitting, Edge Coloring, and Orientations
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• What Can be Computed Locally?
• On the Complexity of Distributed Network Decomposition
• Some simple distributed algorithms for sparse networks
• Locally-Iterative Distributed (Δ+ 1)
• An optimal distributed (Δ+1)-coloring algorithm?
• A lower bound for the distributed Lovász local lemma
• (2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Byzantine agreement in polynomial expected time
• Distributed algorithms for the Lovász local lemma and graph coloring
• Improved deterministic distributed matching via rounding
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy

This page was built for publication: An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model