An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
From MaRDI portal
Publication:4620411
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
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
This page was built for publication: An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
