Random walks that find perfect objects and the Lovász local lemma

DOI10.1145/2818352MaRDI QIDQ3177795zbMATH OpenOpenAlexWikidataFDO

Authors Fotis Iliopoulos, D. 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) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lov'{a}sz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.

Recommendations

• scientific article; zbMATH DE number 1775440
• An algorithmic approach to the Lovász local lemma. I
• The local cut lemma
• Deterministic algorithms for the Lovász local lemma
• Directed Lovász local lemma and Shearer's lemma

Cited in

(14)

• Directed Lovász local lemma and Shearer's lemma
• The list chromatic number of graphs with small clique number
• Combinatorial constructions of separating codes
• The local cut lemma
• New bounds for the Moser-Tardos distribution
• Counting hypergraph colorings in the local lemma regime
• Stochastic control via entropy compression
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• A local lemma for focused stochastic algorithms
• A time hierarchy theorem for the LOCAL model
• Finding independent transversals efficiently
• Commutative algorithms approximate the LLL-distribution
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• An algorithmic proof of the Lovász local lemma via resampling oracles

This page was built for publication: Random walks that find perfect objects and the Lovász local lemma

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