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

DOI10.1145/2818352zbMATH Open1426.05154arXiv1406.0242OpenAlexW2006557844WikidataQ124802243 ScholiaQ124802243MaRDI QIDQ3177795FDOQ3177795

Authors: Fotis Iliopoulos, D. Achlioptas 

Publication date: 2 August 2018

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

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.

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

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

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)

Cited In (14)

• 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
• A time hierarchy theorem for the LOCAL model
• Commutative algorithms approximate the LLL-distribution
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Stochastic control via entropy compression
• Finding independent transversals efficiently
• 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)