[cs-talks] FW: invitation to talk at BU

cs, Group cs at bu.edu
Thu Nov 16 11:05:13 EST 2017


Hi CS!

Please see the information below regarding an upcoming presentation, “Random Walks That Find Perfect Objects and the Lovasz Local Lemma”, this Monday, November 20th.

Best,
Emma

Office Assistant
--
Department of Computer Science
Boston University
111 Cummington Mall, Rm. 138
(617) 353-8919
cs at bu.edu

--------------------

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)

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 Fotis Iliopoulos.

Bio
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...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20171116/cd5bb6f1/attachment.html>


More information about the cs-talks mailing list