An Extension of the Moser--Tardos Algorithmic Local Lemma
An Extension of the Moser--Tardos Algorithmic Local Lemma
A recent theorem of Bissacot et al. [arXiv:0910.1824v2, 2010], proved using results about the cluster expansion in statistical mechanics, extends the Lovász local lemma by weakening the conditions under which its conclusion holds. In this note, we prove an algorithmic analogue of this result, extending Moser and Tardos's recent algorithmic …