Computer Science/Discrete Mathematics Seminar I | |

Topic: | Approximate counting and the Lovasz local lemma |

Speaker: | Ankur Moitra |

Affiliation: | Massachusetts Institute of Technology |

Date: | Monday, March 20 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2017/0320-AnkurMoitra |

We introduce a new approach for approximately counting in bounded degree systems with higher-order constraints. 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. Moreover 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. Our program is a significant departure from earlier techniques in approximate counting, and is a based on a framework to bootstrap an oracle for computing marginal probabilities on individual variables.