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)

• An algorithmic proof of the Lovász local lemma via resampling oracles
• 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
• Distributed algorithms for the Lovász local lemma and graph coloring
• Fundamentals of partial rejection sampling
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• An improvement of the Lovász local lemma via cluster expansion
• A local lemma for focused stochastic algorithms
• New bounds for the Moser-Tardos distribution
• Rainbow Hamilton cycles and lopsidependency
• The local cut lemma
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• An algorithmic version of the blow-up lemma
• Commutative algorithms approximate the LLL-distribution
• Extremal bipartite independence number and balanced coloring
• Finding independent transversals efficiently

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)