A Time Hierarchy Theorem for the LOCAL Model

DOI10.1137/17M1157957zbMath1405.68116arXiv1704.06297OpenAlexW2907309485WikidataQ128644983 ScholiaQ128644983MaRDI QIDQ4646447

Seth Pettie, Yi-Jun Chang

Publication date: 14 January 2019

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

Full work available at URL: https://arxiv.org/abs/1704.06297

zbMATH Keywords

Lovász local lemmatime hierarchy theoremdistributed local modellocal checkable labeling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (11)

Locally checkable problems in rooted trees ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ 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 Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Local mending ⋮ Distributed algorithms for fractional coloring ⋮ Distributed graph problems through an automata-theoretic Lens

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data structures for distributed counting
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• Distributed coloring algorithms for triangle-free graphs
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• On the Distributed Complexity of Computing Maximal Matchings
• Survey of local algorithms
• Local Computation
• The Locality of Distributed Symmetry Breaking
• Random Walks That Find Perfect Objects and the Lovász Local Lemma
• A constructive proof of the general lovász local lemma
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs
• 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?
• Lopsidependency in the Moser-Tardos Framework
• On the complexity of local distributed graph problems
• Almost global problems in the LOCAL model
• On the complexity of distributed graph coloring
• New classes of distributed time complexity
• On the Computational Complexity of Algorithms
• A lower bound for the distributed Lovász local lemma
• Brief Announcement
• LCL Problems on Grids
• A constructive algorithm for the Lovász Local Lemma on permutations
• Towards a complexity theory for local distributed computing
• Moser and tardos meet Lovász
• Distributed algorithms for the Lovász local lemma and graph coloring

This page was built for publication: A Time Hierarchy Theorem for the LOCAL Model