<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div style="color:rgb(80,0,80)"><div class="gmail_default" style="color:rgb(34,34,34)"><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><div style="color:rgb(80,0,80)"><br></div><div style="color:rgb(80,0,80)"><br></div><div><font color="#000000"><b>Title:</b> Sandwich to Sample Exactly</font></div><div><font color="#000000"><br></font></div><div><font face="arial, sans-serif" color="#000000"><div><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.<br><br>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. 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. </div><div><br></div></font><div><font face="arial, sans-serif" color="#000000">In particular, for sampling colorings, our work (Bhandari and Chakraborty) makes the exact sampling requirement on the number of colors from quadratic in the maximum degree of the graph to linear: hence, we make exact sampling comparable to the best approximate sampling results. For the case of independent sets, we (Bhandari, Chakraborty and Srivastava) show an efficient exact sampling algorithm all the way till the tree uniqueness threshold for graphs with large girth and degrees at least logarithmic in the number of vertices: this is a common setting for the various results in the approximate sampling paradigm. Prior to this work no results were known where 'local-uniformity' techniques for proving fast mixing of chains were lifted to exact sampling. </font></div></div><div style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div><div><font face="arial, sans-serif"><b>Bio: </b> Siddharth Bhandari is a fifth year graduate student in the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai. Siddharth is pursuing his Ph.D. under the guidance of Prof. Prahladh Harsha. Previously, he obtained a B.Tech.degree in Mechanical Engineering from IIT, Kharagpur and a M.Sc. degree in Computer Science from CMI.</font></div></div><div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">His research interests lie broadly in the field of randomized computation. He has dabbled in zero-error information theory, coding theory, sampling algorithms and theoretical guarantees for generative networks. Website: <a href="https://sites.google.com/view/siddharth-bhandari/home" target="_blank">https://sites.google.com/view/siddharth-bhandari/home</a></font></div></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a><br></font></div><div><br></div><div><br style="color:rgb(80,0,80)"></div></div><div><div dir="ltr" class="gmail_signature" 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></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Mar 24, 2021 at 10:00 AM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div style="color:rgb(80,0,80)"><div style="color:rgb(34,34,34)"><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><div style="color:rgb(80,0,80)"><br></div><div style="color:rgb(80,0,80)"><br></div><div><font color="#000000"><b>Title:</b> Sandwich to Sample Exactly</font></div><div><font color="#000000"><br></font></div><div><font face="arial, sans-serif" color="#000000"><div><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.<br><br>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. 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. </div><div><br></div></font><div><font face="arial, sans-serif" color="#000000">In particular, for sampling colorings, our work (Bhandari and Chakraborty) makes the exact sampling requirement on the number of colors from quadratic in the maximum degree of the graph to linear: hence, we make exact sampling comparable to the best approximate sampling results. For the case of independent sets, we (Bhandari, Chakraborty and Srivastava) show an efficient exact sampling algorithm all the way till the tree uniqueness threshold for graphs with large girth and degrees at least logarithmic in the number of vertices: this is a common setting for the various results in the approximate sampling paradigm. Prior to this work no results were known where 'local-uniformity' techniques for proving fast mixing of chains were lifted to exact sampling. </font></div></div><div style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div><div><font face="arial, sans-serif"><b>Bio: </b> Siddharth Bhandari is a fifth year graduate student in the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai. Siddharth is pursuing his Ph.D. under the guidance of Prof. Prahladh Harsha. Previously, he obtained a B.Tech.degree in Mechanical Engineering from IIT, Kharagpur and a M.Sc. degree in Computer Science from CMI.</font></div></div><div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">His research interests lie broadly in the field of randomized computation. He has dabbled in zero-error information theory, coding theory, sampling algorithms and theoretical guarantees for generative networks. Website: <a href="https://sites.google.com/view/siddharth-bhandari/home" target="_blank">https://sites.google.com/view/siddharth-bhandari/home</a></font></div></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a><br></font></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr"><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></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Mar 23, 2021 at 5:06 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><div style="color:rgb(80,0,80);font-size:small"><div style="color:rgb(34,34,34)"><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><div style="color:rgb(80,0,80);font-size:small"><br></div><div style="color:rgb(80,0,80);font-size:small"><br></div><div style="font-size:small"><font color="#000000"><b>Title:</b> Sandwich to Sample Exactly</font></div><div style="font-size:small"><font color="#000000"><br></font></div><div><span><font face="arial, sans-serif" color="#000000"><div><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.<br><br>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. 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. </div><div><br></div></font></span><div><font face="arial, sans-serif" color="#000000">In particular, for sampling colorings, our work (Bhandari and Chakraborty) makes the exact sampling requirement on the number of colors from quadratic in the maximum degree of the graph to linear: hence, we make exact sampling comparable to the best approximate sampling results. For the case of independent sets, we (Bhandari, Chakraborty and Srivastava) show an efficient exact sampling algorithm all the way till the tree uniqueness threshold for graphs with large girth and degrees at least logarithmic in the number of vertices: this is a common setting for the various results in the approximate sampling paradigm. Prior to this work no results were known where 'local-uniformity' techniques for proving fast mixing of chains were lifted to exact sampling. </font></div></div><div style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div><div><font face="arial, sans-serif"><b>Bio: </b>
Siddharth Bhandari is a fifth year graduate student in the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai.
Siddharth is pursuing his Ph.D. under the guidance of Prof. Prahladh Harsha. Previously, he obtained a B.Tech.degree in Mechanical Engineering from IIT, Kharagpur and a M.Sc. degree in Computer Science from CMI.</font></div></div><div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">His research interests lie broadly in the field of randomized computation. He has dabbled in zero-error information theory, coding theory, sampling algorithms and theoretical guarantees for generative networks. Website: <a href="https://sites.google.com/view/siddharth-bhandari/home" target="_blank">https://sites.google.com/view/siddharth-bhandari/home</a></font></div></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a><br></font></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div><div><div dir="ltr"><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></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Mar 19, 2021 at 2:37 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-size:small"><div><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 style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(80,0,80)"><font face="arial, sans-serif"><br></font></div><div 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 style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><font face="arial, sans-serif"><br></font></span></div><div 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 style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><br></span></div><div style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><br></span></div><div style="color:rgb(80,0,80)"><span style="color:rgb(34,34,34)"><br></span></div><br></div><div><div dir="ltr"><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"><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>
</blockquote></div>
</div>
</blockquote></div></div>
</blockquote></div></div>