A constructive proof of the general lovász local lemma

By Robin A. Moser, Gábor Tardos. JACM, 2009

590 citations recorded by the source corpus.

The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/57c88a797213efdd98ec64d6c16a29ef2af64621

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

The Locality of Distributed Symmetry Breaking (2012, methodology): “The fastest known deterministic decomposition algorithm is due to Panconesi and Srinivasan [1996]. See Awerbuch et al.”
Small cancellation labellings of some infinite graphs and applications (2014, methodology): “elatively short (pp. 5{16 below) compared to Gromov’s one as presented in [AD08]. Finally, although our method is probabilistic, there exist constructive versions of the Lovasz Local Lemma; see e.g. [MT10]. This allows one to provide an algorithm producing the labeling. Below we describe the actual ”
THE LOGARITHMICALLY AVERAGED CHOWLA AND ELLIOTT CONJECTURES FOR TWO-POINT CORRELATIONS (2015, background): “To get around this obstacle we introduce a new argument which we call the ‘entropy decrement argument’ (in analogy with the ‘density increment argument’ and ‘energy increment argument’ that appear in the literature surrounding Szemerédi’s theorem on arithmetic progressions (see for example [29]), a”