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

DOI10.4230/LIPICS.DISC.2017.18zbMATH Open1515.68367MaRDI QIDQ6487489FDOQ6487489

Authors: Manuela Fischer, Mohsen Ghaffari 

Publication date: 3 February 2023

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

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)

Cited In (24)

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

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)