Random walks that find perfect objects and the Lovász local lemma

Computer Science/Discrete Mathematics Seminar I
Topic:Random walks that find perfect objects and the Lovász local lemma
Speaker:Dimitris Achlioptas
Affiliation:University of California, Santa Cruz
Date:Monday, March 23
Time/Room:11:15am - 12:15pm/S-101
Video Link:http://video.ias.edu/csdm/2015/0323-DimitrisAchlioptas

At the heart of every local search algorithm is a directed graph on candidate solutions (states) such that every unsatisfactory state has at least one outgoing arc. In stochastic local search the hope is that a random walk will reach a satisfactory state (sink) quickly. We give a general algorithmic local lemma by establishing a sufficient condition for this to be true. Our work is inspired by Moser's entropic method proof of the Lovász Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. Similarly to Moser's argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time. Based on joint work with Fotis Iliopoulos.