Approximate Counting

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.