Computer Science Department
University of Rochester
Counting problems arise in a wide variety of areas, for example, enumerative combinatorics, statistical physics, and estimating probabilities in graphical models. I will talk about the algorithmic aspects of approximate counting, focusing on:
1) the connection between counting and sampling---an extension of the Monte Carlo technique that efficiently translates sampling algorithms into counting algorithms
2) algorithmic techniques used to design counting algorithms, for example, Markov chains and dynamic programming.