An extension of the Moser-Tardos algorithmic local lemma

DOI10.1137/110828290zbMATH Open1301.60013arXiv1102.2853OpenAlexW2963097814WikidataQ124877411 ScholiaQ124877411MaRDI QIDQ3192170FDOQ3192170

Wesley Pegden

Publication date: 26 September 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A recent theorem of Bissacot, et al. proved using results about the cluster expansion in statistical mechanics extends the Lov'asz Local Lemma by weakening the conditions under which its conclusions holds. In this note, we prove an algorithmic analog of this result, extending Moser and Tardos's recent algorithmic Local Lemma, and providing an alternative proof of the theorem of Bissacot, et al. applicable in the Moser-Tardos algorithmic framework.

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

zbMATH Keywords

algorithmpartition functionlocal lemma

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (16)

• Commutativity in the Algorithmic Lovász Local Lemma
• Entropy compression versus Lovász local lemma
• Virial series for a system of classical particles interacting through a pair potential with negative minimum
• New bounds for the Moser‐Tardos distribution
• A Local Lemma for Focused Stochastic Algorithms
• Distributed algorithms for the Lovász local lemma and graph coloring
• Fundamentals of partial rejection sampling
• Title not available (Why is that?)
• An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• Rainbow Hamilton cycles and lopsidependency
• The local cut lemma
• An algorithmic version of the blow-up lemma
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Extremal bipartite independence number and balanced coloring
• Finding independent transversals efficiently

   Recommendations

• Moser and tardos meet Lovász 👍 👎
• Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion 👍 👎
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas 👍 👎
• Directed Lovász local lemma and Shearer's lemma 👍 👎
• New constructive aspects of the Lovász local lemma 👍 👎

This page was built for publication: An extension of the Moser-Tardos algorithmic local lemma

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