<div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, October 30th at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr" style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:      </font><font face="arial, helvetica, sans-serif">Ankur Moitra, MIT</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px">Title:       <span style="font-size:12.8px">A New Approach to Approximate Counting and Sampling</span></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:Arial,sans-serif;font-size:small;white-space:pre-wrap">Abstract: </span><span style="font-size:12.8px">Abstract: Over the past sixty years, many remarkable connections</span><span style="color:rgb(0,0,0);font-family:Arial,sans-serif;font-size:small;white-space:pre-wrap;background-color:rgb(255,247,215)">
</span></div><span style="font-size:12.8px">have been made between statistical physics, probability, analysis and theoretical computer science through the study of approximate counting. While tight phase transitions are known for many problems with pairwise constraints, much less is known about problems with higher-order constraints.</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span style="font-size:12.8px">Here we introduce a new approach for approximately counting and sampling in bounded degree systems. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the number of variables per clause. Our algorithm extends straightforwardly to approximate sampling, which shows that under Lovasz Local Lemma-like conditions, it is possible to generate a satisfying assignment approximately uniformly at random. In our setting, the solution space is not even connected and we introduce alternatives to the usual Markov chain paradigm.</span><br style="font-size:12.8px"></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: <a href="mailto:nati@ttic.edu" target="_blank">Nathan Srebro</a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">For more information on the </span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">colloquium</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" target="_blank" style="font-family:arial,helvetica,sans-serif;font-size:12.8px">http://www.ttic.edu/colloq<wbr>uium.php</a></div><div style="font-size:12.8px"><br></div></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"><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">Administrative Assistant</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 504</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>
<br><div class="gmail_quote">On Sun, Oct 29, 2017 at 8:10 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, October 30th at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:      </font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Ankur Moitra, MIT</span></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px">Title:       <span style="font-size:12.8px">A New Approach to Approximate Counting and Sampling</span></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:Arial,sans-serif;font-size:small;white-space:pre-wrap">Abstract: </span><span style="font-size:12.8px">Abstract: Over the past sixty years, many remarkable connections</span><span style="color:rgb(0,0,0);font-family:Arial,sans-serif;font-size:small;white-space:pre-wrap;background-color:rgb(255,247,215)">
</span></div><span style="font-size:12.8px">have been made between statistical physics, probability, analysis and theoretical computer science through the study of approximate counting. While tight phase transitions are known for many problems with pairwise constraints, much less is known about problems with higher-order constraints.</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span style="font-size:12.8px">Here we introduce a new approach for approximately counting and sampling in bounded degree systems. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the number of variables per clause. Our algorithm extends straightforwardly to approximate sampling, which shows that under Lovasz Local Lemma-like conditions, it is possible to generate a satisfying assignment approximately uniformly at random. In our setting, the solution space is not even connected and we introduce alternatives to the usual Markov chain paradigm.</span><br style="font-size:12.8px"></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: <a href="mailto:nati@ttic.edu" target="_blank">Nathan Srebro</a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">For more information on the </span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">colloquium</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" style="font-family:arial,helvetica,sans-serif;font-size:12.8px" target="_blank">http://www.ttic.edu/colloq<wbr>uium.php</a></div><div style="font-size:12.8px"><br></div></div></div><div class="gmail_extra"><br clear="all"><div><div class="m_3625580121374772648gmail_signature" data-smartmail="gmail_signature"><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">Administrative Assistant</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 504</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:<a href="tel:(773)%20834-1757" value="+17738341757" target="_blank">(773) 834-1757</a></font></i></div><div><i><font face="arial, helvetica, sans-serif">f: <a href="tel:(773)%20357-6970" value="+17733576970" target="_blank">(773) 357-6970</a></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>
<br><div class="gmail_quote">On Mon, Oct 23, 2017 at 6:14 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, October 30th at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:      </font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Ankur Moitra, MIT</span></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px">Title:       <span style="font-size:12.8px">A New Approach to Approximate Counting and Sampling</span></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:Arial,sans-serif;font-size:small;white-space:pre-wrap">Abstract: </span><span style="font-size:12.8px">Abstract: Over the past sixty years, many remarkable connections</span><span style="color:rgb(0,0,0);font-family:Arial,sans-serif;font-size:small;white-space:pre-wrap;background-color:rgb(255,247,215)">
</span></div><span style="font-size:12.8px">have been made between statistical physics, probability, analysis and theoretical computer science through the study of approximate counting. While tight phase transitions are known for many problems with pairwise constraints, much less is known about problems with higher-order constraints.</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span style="font-size:12.8px">Here we introduce a new approach for approximately counting and sampling in bounded degree systems. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the number of variables per clause. Our algorithm extends straightforwardly to approximate sampling, which shows that under Lovasz Local Lemma-like conditions, it is possible to generate a satisfying assignment approximately uniformly at random. In our setting, the solution space is not even connected and we introduce alternatives to the usual Markov chain paradigm.</span><br style="font-size:12.8px"></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: <a href="mailto:nati@ttic.edu" target="_blank">Nathan Srebro</a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">For more information on the </span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">colloquium</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" style="font-family:arial,helvetica,sans-serif;font-size:12.8px" target="_blank">http://www.ttic.edu/colloq<wbr>uium.php</a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div></div></div><div><div class="m_3625580121374772648m_-320963923368338216gmail_signature"><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">Administrative Assistant</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 504</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:<a href="tel:(773)%20834-1757" value="+17738341757" target="_blank">(773) 834-1757</a></font></i></div><div><i><font face="arial, helvetica, sans-serif">f: <a href="tel:(773)%20357-6970" value="+17733576970" target="_blank">(773) 357-6970</a></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>
</blockquote></div><br></div></div>
</blockquote></div><br></div></div>