2011

An extension of the Moser-Tardos algorithmic local lemma

Pegden, Wesley

Understand

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.

P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite sets
1975
Earlier work this paper cites.
J. Shearer. On a problem of Spencer, Combinatorica
1985
Earlier work this paper cites.
N. Alon. A parallel algorithmic version of the local lemma, Random Structures and Algorithms
1991
Earlier work this paper cites.
Jószef Beck. An Algorithmic Approach to the Lovász Local Lemma, Random Structures and Algorithms 2
1991
Earlier work this paper cites.

P. Erdős, J. Spencer. Lopsided Lovász Local Lemma and Latin transversals, Discrete Applied Math. 30
1991
Cited alongside, same era.
M. Molloy and B. Reed. Further Algorithmic Aspects of the Local Lemma, Proceedings of the 30th Annual ACM Symposium on the Theory of Computing
1998
Cited alongside, same era.
A. Czumaj and C. Scheideler. Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma, Symposium on Discrete Algorithms
2000
Cited alongside, same era.
A. Scott and A. Sokal. The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys
2005
Cited alongside, same era.
R. Bissacot, R. Fernández, A. Procacci, B. Scoppola. Title: An Improvement of the Lovász Local Lemma via Cluster Expansion. http://arxiv.org/abs/0910.1824v2
Original
Cited in the paper.
S. Ndreca, A. Procacci, B. Scoppola. Improved bounds on coloring of graphs, http://arxiv.org/abs/1005.1875
Original
Cited in the paper.

R. Fernandez, A. Procacci. Cluster expansion for abstract polymer models: New bounds from an old approach. Communications in Mathematical Physics
2007
Later among the works it cites.
A. Srinivasan. Improved algorithmic versions of the Lovász Local Lemma, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA)
2008
Later among the works it cites.
K. Kolipaka, M. Szegedy. Moser and Tardos meet Lovász. Manuscript (2010)
2010
Later among the works it cites.
R. Moser and G. Tardos. A constructive proof of the general Lovász Local Lemma, J. ACM
2010
Later among the works it cites.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…