Random Walks That Find Perfect Objects and the Lovász Local Lemma

DOI10.1145/2818352zbMath1426.05154arXiv1406.0242OpenAlexW2006557844WikidataQ124802243 ScholiaQ124802243MaRDI QIDQ3177795

Fotis Iliopoulos, Demetrios Achlioptas

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

Lovász local lemmaentropic method

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Random walks on graphs (05C81)

Related Items (11)

The list chromatic number of graphs with small clique number ⋮ Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Directed Lovász local lemma and Shearer's lemma ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Finding independent transversals efficiently ⋮ A Local Lemma for Focused Stochastic Algorithms

This page was built for publication: Random Walks That Find Perfect Objects and the Lovász Local Lemma