Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
From MaRDI portal
Publication:6487489
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)