<div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Wednesday, March 24th at<b> 11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b> </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_cxTpN_kyT2WC_2F8fNWj2g" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> </font></font><font color="#000000">Siddharth Bhandari, Tata Institute of Fundamental Research, India</font></font></p></div><div class="gmail_default" style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div class="gmail_default" style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div class="gmail_default" style="color:rgb(80,0,80)"><font face="arial, sans-serif"><span style="color:rgb(34,34,34)"><b>Title:</b> Sandwich to Sample Exactly<br><br></span><span style="color:rgb(34,34,34)"><b>Abstract:</b> In this talk, we will look at recent progress on "exact sampling" of two central problems: Graph Colorings and Independent Sets. The classical algorithms for approximately sampling from the corresponding Gibb's Distribution involve running the appropriate Glauber Dynamics (GD) for a fixed amount of time depending on the input size and outputting a sample whose distribution is close to the corresponding Gibb's Distribution. The quantity of interest then, is the mixing time of the GD which quantifies how fast the chain converges to the stationary distribution starting from an arbitrary initial configuration.</span><br style="color:rgb(34,34,34)"><br style="color:rgb(34,34,34)"><span style="color:rgb(34,34,34)">However, the above algorithms only produce approximate samples. Thus, it is natural to ask if we can efficiently produce a sample that is distributed exactly according to the Gibb's Distribution. Apart from its independent theoretical appeal, exact sampling algorithms potentially yield faster FPRASs and provide exact samples even in the absence of guarantees on the mixing time.</span><br style="color:rgb(34,34,34)"><br style="color:rgb(34,34,34)"><span style="color:rgb(34,34,34)">The intriguing fact that exact sampling is in general possible using Markov Chains was established by Propp and Wilson'96 in a seminal work which introduced the technique of Coupling from the Past (CFTP). This, coupled with the Bounding Chain technique of Huber'98, and Haggstrom & Nelander'99, lets us use the GD to efficiently sample exactly from the Gibb's Distribution for the case of colorings and independent sets, however, for a much-restricted set of parameters as compared to the approximate sampling counterparts. We will see how to bridge this gap between approximate and exact sampling for these fundamental problems.</span><br style="color:rgb(34,34,34)"></font></div><div class="gmail_default" style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><font face="arial, sans-serif"><br></font></span></div><div class="gmail_default" style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></font></span></div><div class="gmail_default" style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><br></span></div><div class="gmail_default" style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><br></span></div><div class="gmail_default" style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><br></span></div><br></div><div><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr"><div><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</div></div>