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

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

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

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 (12)

• The list chromatic number of graphs with small clique number
• New bounds for the Moser‐Tardos distribution
• A Local Lemma for Focused Stochastic Algorithms
• Directed Lovász local lemma and Shearer's lemma
• A Time Hierarchy Theorem for the LOCAL Model
• Title not available (Why is that?)
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
• Counting Hypergraph Colorings in the Local Lemma Regime
• Combinatorial constructions of separating codes
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• 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)