Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy

DOI10.4230/LIPICS.DISC.2017.18MaRDI QIDQ6487489zbMATH OpenFDO

Authors Manuela Fischer, Mohsen Ghaffari

Publication date 3 February 2023

zbMATH Keywords

distributed graph algorithmsfrugal coloringdefective coloringLovász local lemmalocally checkable labeling problemslist vertex-coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

Recommendations

• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed algorithms for the Lovász local lemma and graph coloring
• A lower bound for the distributed Lovász local lemma
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• A time hierarchy theorem for the LOCAL model

Cited in

(22)

• The complexity landscape of distributed locally checkable problems on trees
• Distributed graph problems through an automata-theoretic lens
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
• scientific article; zbMATH DE number 7559119 (Why is no real title available?)
• Improved distributed \(\Delta\)-coloring
• Classification of distributed binary labeling problems
• Factor-of-iid balanced orientation of non-amenable graphs
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Distributed graph problems through an automata-theoretic Lens
• A lower bound for the distributed Lovász local lemma
• Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma
• Component stability in low-space massively parallel computation
• A time hierarchy theorem for the LOCAL model
• Node and edge averaged complexities of local graph problems
• Finding independent transversals efficiently
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed coloring of hypergraphs
• Equivariant maps to subshifts whose points have small stabilizers

This page was built for publication: Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy

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