BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Conferences/Seminars/Lectures
DESCRIPTION:Ankur Moitra  (MIT)\n\nA New Approach to Approximate Counting a
 nd Sampling\n\nOver the past sixty years\, many remarkable connections have
  been made between statistical physics\, probability\, analysis and theoret
 ical computer science through the study of approximate counting. While tigh
 t phase transitions are known for many problems with pairwise constraints\,
  much less is known about problems with higher-order constraints.\n\nHere w
 e introduce a new approach for approximately counting and sampling in bound
 ed degree systems. Our main result is an algorithm to approximately count t
 he 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 c
 onditions\, it is possible to generate a satisfying assignment approximatel
 y uniformly at random. In our setting\, the solution space is not even conn
 ected and we introduce alternatives to the usual Markov chain paradigm.
DTEND:20181029T211500Z
DTSTAMP:20260412T170742Z
DTSTART:20181029T201500Z
LOCATION:2-147\, 2-147
SEQUENCE:0
SUMMARY:Probability Seminar
UID:tag:localist.com\,2008:EventInstance_4050171
URL:https://calendar.mit.edu/event/probability_seminar_1712
END:VEVENT
END:VCALENDAR