<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div class=""><span class="" style="font-size: 14px;"><b class="" style="font-family: LucidaGrande; background-color: rgba(255, 255, 255, 0);"><u class="">Department of Computer Science </u></b><b class="" style="background-color: rgba(255, 255, 255, 0); font-family: LucidaGrande;"><u class="">Seminar</u></b></span></div></div><div class="" style="font-family: LucidaGrande;"><span class="" style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Monday, March 6, 2017</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">2:30 pm</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Ryerson 251 </span></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Heng Guo</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">(Queen Mary, University of London)</span></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class=""><span class="" style="font-size: 14px;"><span class="" style="font-family: LucidaGrande;">Title: </span><span class="" style="font-family: LucidaGrande;">Computational counting and sampling</span><br class="gmail-m_4827095062818533991gmail_msg"><br class="gmail-m_4827095062818533991gmail_msg"><span class="" style="font-family: LucidaGrande;">Abstract: </span></span></div><div class=""><font face="LucidaGrande" class=""><span class=""><span class=""><span class="" style="font-size: 14px;">Computational counting and sampling have been studied since the dawn of computer science, in the context of statistical physics simulations.<br class="">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<br class="">recent progress on sampling algorithms. First, we will talk about the classical Markov chain approach and show the first polynomial mixing time<br class="">bound for the Swendsen-Wang (1987) algorithm in ferromagnetic Ising models. Then we will turn to a new resampling approach to uniformly sample satisfying<br class="">assignments for CNF formulas under locality conditions. The resampling approach has an intimate connection with the Moser-Tardos (2010) algorithm for<br class="">the Lovasz Local Lemma.<br class=""><br class=""><br class=""></span><span class="" style="font-size: 14px;">-----</span><br class=""></span><span class="" style="font-size: 14px;"> </span><span class="" style="font-size: 14px;"><br class=""></span></span></font><span class="" style="font-size: 14px;"><span class="" style="font-family: 'Lucida Grande';">Bio: </span></span><span class="" style="font-family: LucidaGrande; font-size: 14px;">Heng Guo is currently a postdoctoral researcher at Queen Mary, University of </span><span class="" style="font-family: LucidaGrande; font-size: 14px;">London, working with Mark Jerrum. He came to London after finishing his Ph.D.</span><br class="" style="font-family: LucidaGrande; font-size: 14px;"><span class="" style="font-family: LucidaGrande; font-size: 14px;">at the University of Wisconsin - Madison in 2015, and spending a semester at </span><span class="" style="font-family: LucidaGrande; font-size: 14px;">UC-Berkeley as a Google research fellow. His research focuses on mapping the</span><br class="" style="font-family: LucidaGrande; font-size: 14px;"><span class="" style="font-family: LucidaGrande; font-size: 14px;">algorithmic boundary of counting and sampling problems. He received the </span><span class="" style="font-family: LucidaGrande; font-size: 14px;">2016 EATCS Distinguished Dissertation award and the Simons award for graduate</span><br class="" style="font-family: LucidaGrande; font-size: 14px;"><span class="" style="font-family: LucidaGrande; font-size: 14px;">students in TCS (2013-2015).</span><div class=""><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Host: Ketan Mulmuley</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class="" style="font-family: LucidaGrande;"><font size="2" class="">Refreshments in Ry. 255 after the talk</font></div></div></div></body></html>