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)

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

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)