On the Locality of the Lovász Local Lemma

Peter Davies-Peck ( Durham University )

The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set of underlying random variables, can be avoided. It is a central tool of the probabilistic method, since it can be used to show that combinatorial objects satisfying some desirable properties must exist. While the original proof was existential, subsequent work has shown algorithms for the Lovász Local Lemma: that is, in circumstances in which the lemma proves the existence of some object, these algorithms can constructively find such an object. One main strand of these algorithms, which began with Moser and Tardos’s well-known result, involves iteratively resampling the dependent variables of satisfied bad events until none remain satisfied.

In this talk, we will discuss a novel analysis that can be applied to resampling-style Lovász Local Lemma algorithms. This analysis shows that an output assignment for the dependent variables of most events can be determined only from low-radius local neighborhoods, and that the events whose variables may still require resampling can be identified from these neighborhoods. This allows us to improve randomised complexities for the constructive Lovász Local Lemma in several parallel and distributed models.