[Colloquium] 10/30 TTIC Colloquium: Ankur Moitra, MIT

[Mary Marre via Colloquium]

When:     Monday, October 30th at 11:00 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526

Who:      Ankur Moitra, MIT


Title:       A New Approach to Approximate Counting and Sampling

Abstract: Abstract: Over the past sixty years, many remarkable connections
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.

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.


Host: Nathan Srebro <nati at ttic.edu>


For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20171023/673720e2/attachment.html>