[Colloquium] CS Seminar on March 6: Heng Guo, Queen Mary, University of London

[Sandra Wallace via Colloquium]

Department of Computer Science Seminar

Monday, March 6, 2017
2:30 pm
Ryerson 251 

Heng Guo
(Queen Mary, University of London)

Title: Computational counting and sampling

Abstract: 
Computational counting and sampling have been studied since the dawn of computer science, in the context of statistical physics simulations.
Since then, a wide range of applications has been found, most notably in statistical inference and machine learning. In this talk, we will cover some
recent progress on sampling algorithms. First, we will talk about the classical Markov chain approach and show the first polynomial mixing time
bound for the Swendsen-Wang (1987) algorithm in ferromagnetic Ising models. Then we will turn to a new resampling approach to uniformly sample satisfying
assignments for CNF formulas under locality conditions. The resampling approach has an intimate connection with the Moser-Tardos (2010) algorithm for
the Lovasz Local Lemma.


-----
 
Bio:  Heng Guo is currently a postdoctoral researcher in Queen Mary, University of London, working with Mark Jerrum. He came to London after finishing his Ph.D.
at the University of Wisconsin - Madison in 2015, and spending a semester at UC-Berkeley as a Google research fellow. His research focuses on mapping the
algorithmic boundary of counting and sampling problems. He received the 2016 EATCS Distinguished Dissertation award and the Simons award for graduate
students in TCS (2013-2015).


Host: Ketan Mulmuley

Refreshments in Ry. 255 after the talk
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170224/47545b57/attachment.html>