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 -