New Constructive Aspects of the Lovasz Local Lemma

ABSTRACT: The Lovasz Local Lemma (LLL) is a powerful tool that
gives sufficient conditions for avoiding all of a given set of
``bad'' events. A series of results have provided algorithmic
versions of the LLL, culminating in the recent breakthrough of
Moser and Tardos (MT). We show that the output distribution of
MT well-approximates the distribution obtained by conditioning
on all bad events being avoided. We also show that when an LLL
application provides a small amount of slack, the number of
resamplings of MT 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 LLL is applied
to super-polynomially many events. Even in situations 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 these ideas on applications including the first
constant-factor approximation algorithm for the Santa Claus
problem, and various graph-coloring problems. As a second type
of application, we develop a (constructive) version of the LLL
that allows a small fraction of bad events to happen: MAX-SAT
is an illustrative example.

Joint work with Bernhard Haeupler (MIT) and Barna Saha (Univ.
of Maryland).

    	
BIO: Aravind Srinivasan is a Professor with the Department of
Computer Science and the Institute for Advanced Computer
Studies at the University of Maryland, College Park. He
received his undergraduate degree from the Indian Institute of
Technology, Madras, and his Ph.D. from Cornell University, both
in Computer Science. He was a postdoctoral researcher at the
Institute for Advanced Study in Princeton and at DIMACS. He has
also worked in industrial research, at Bell Labs.

Aravind Srinivasan's research interests are in randomized
algorithms, networking, social networks, and combinatorial
optimization, as well as in the growing confluence of
algorithms, networks, and randomness in society, in fields
including the social Web and public health. He has published
several papers in these areas, in journals including Nature,
Journal of the ACM, IEEE/ACM Transactions on Networking, and
the SIAM Journal on Computing. He is an editor of four
journals, and has served on the program committees of various
conferences. He was co-recipient of the Best Student Paper
Award at ACM STOC 1992, and received an IBM Graduate Fellowship
during his doctoral studies. He is an IEEE Fellow.