pith. sign in

arxiv: 1102.2853 · v2 · pith:MFGPYVMRnew · submitted 2011-02-14 · 🧮 math.CO · cs.DS

An extension of the Moser-Tardos algorithmic local lemma

classification 🧮 math.CO cs.DS
keywords algorithmiclemmalocalbissacotmoser-tardosrecenttheoremalternative
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.