Tuesday, March 29, 2016 - 4:00pm to Wednesday, March 30, 2016 - 3:55pm
Event Calendar Category
LIDS Seminar Series
Speaker Name
Dimitris Achlioptas
Affiliation
University of California, Santa Cruz
Building and Room Number
32-155
Abstract
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 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.
Joint work with F. Iliopoulos.
Biography
Dimitris Achlioptas is a professor in the Department of Computer Science at UC Santa Cruz and at the University of Athens. Prior to that he was a postdoc and then a researcher at Microsoft Research, Redmond. He is broadly interested in the interaction between randomness and computation and his work on that topic has appeared in journals including Nature, Science, and the Annals of Mathematics. He has received an NSF CAREER award, a Sloan Fellowship, and an ERC Starting Grant.