New Constructive Aspects of the Lovasz Local Lemma

TitleNew Constructive Aspects of the Lovasz Local Lemma
Publication TypeConference Papers
Year of Publication2010
AuthorsHaeupler B, Saha B, Srinivasan A
Conference Name2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)
Date Published2010/10/23/26
PublisherIEEE
ISBN Number978-1-4244-8525-3
Keywordsacyclic edge coloring, Algorithm design and analysis, Approximation algorithms, Approximation methods, computational complexity, Computer science, constant factor approximation algorithm, graph colouring, Linearity, Lovasz Local Lemma, MAX k-SAT, Monte Carlo Algorithm, Monte Carlo methods, Moser-Tardos algorithm, nonrepetitive graph coloring, output distribution, polynomial sized core subset, Polynomials, Probabilistc Method, probabilistic analysis, probabilistic logic, probability, Ramsey type graph, Sampling methods, Santa Claus Problem
Abstract

The Lov'{a}sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of ``bad'' events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emph{conditional LLL-distribution} – the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized ``core'' subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this.

DOI10.1109/FOCS.2010.45