[Cs-affiliates] CS Distinguished Lecture on Monday: Dimitris Achlioptas (UCSC)
orecchia at bu.edu
Thu Nov 16 09:13:20 EST 2017
Please join us this Monday, November 20, for this semester’s CS Distinguished Lecture by Dimitris Achlioptas (UCSC):
When: Monday, 11/20, 10.30am-11.30am
Where: Hariri Institute seminar room
Title: RANDOM WALKS THAT FIND PERFECT OBJECTS AND THE LOVASZ LOCAL LEMMA
Speaker: Dimitris Achlioptas (UCSC)
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 Fotis Iliopoulos.
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Cs-affiliates