An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
The Lovasz Local Lemma (LLL) is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space.
In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original LLL applies, there exist resampling oracles; and for essentially all known applications of the LLL we have designed efficient resampling oracles.
Our analysis is based on an alternative view of the LLL using multivariate polynomials, due to Shearer (and Scott and Sokal). Probabilists have also studied this topic under the name of "1-dependent hard-core processes".
Joint work with Jan Vondrak (IBM Research).