An extension of the Moser-Tardos algorithmic local lemma

DOI10.1137/110828290MaRDI QIDQ3192170zbMATH OpenOpenAlexWikidataFDO

Authors Wesley Pegden

Publication date 26 September 2014

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

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)

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.

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

Cited in

(17)

• Rainbow Hamilton cycles and lopsidependency
• Extremal bipartite independence number and balanced coloring
• Distributed algorithms for the Lovász local lemma and graph coloring
• Fundamentals of partial rejection sampling
• Entropy compression versus Lovász local lemma
• The local cut lemma
• New bounds for the Moser-Tardos distribution
• Commutativity in the Algorithmic Lovász Local Lemma
• An algorithmic version of the blow-up lemma
• A local lemma for focused stochastic algorithms
• An improvement of the Lovász local lemma via cluster expansion
• Finding independent transversals efficiently
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• Virial series for a system of classical particles interacting through a pair potential with negative minimum
• 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: 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)