TY - CONF T1 - New Constructive Aspects of the Lovasz Local Lemma T2 - 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) Y1 - 2010 A1 - Haeupler,B. A1 - Saha,B. A1 - Srinivasan, Aravind KW - acyclic edge coloring KW - Algorithm design and analysis KW - Approximation algorithms KW - Approximation methods KW - computational complexity KW - Computer science KW - constant factor approximation algorithm KW - graph colouring KW - Linearity KW - Lovasz Local Lemma KW - MAX k-SAT KW - Monte Carlo Algorithm KW - Monte Carlo methods KW - Moser-Tardos algorithm KW - nonrepetitive graph coloring KW - output distribution KW - polynomial sized core subset KW - Polynomials KW - Probabilistc Method KW - probabilistic analysis KW - probabilistic logic KW - probability KW - Ramsey type graph KW - Sampling methods KW - Santa Claus Problem AB - 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. JA - 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) PB - IEEE SN - 978-1-4244-8525-3 M3 - 10.1109/FOCS.2010.45 ER -