Approximate Counting

   Lecture 1: Approximate Counting I
   Lecture 2: Approximate Counting II
   
 

This series of talks is part of the Counting Complexity and Phase Transitions Boot Camp. 

Speaker: Leslie Ann Goldberg (University of Oxford) and David Richerby (University of Oxford)

Computational counting problems involve computing weighted sums such as the value of an integral, the expectation of a random variable, or the partition function of a spin model. This mini-course is a survey on the complexity of approximately solving such counting problems. The talks will be accessible to people who have no background in counting complexity. The first session will focus particularly on the complexity of approximate counting within #P (or at least within FP^#P) and will pay particular attention to the role of the intermediate problem #BIS. The second session will focus particularly on the complexity of approximate counting within the domain of Constraint Satisfaction Problems.