Title: The Complexity of Approximate Counting
Abstract: Computational counting problems
arise in applications such as statistics, statistical physics, coding, and machine learning.
In such a problem, a numerical quantity (a weighted sum) is computed, either exactly or approximately. Examples include computing (or estimating) an integral, a probability, or the expectation of a random variable.
Work in computational complexity aims to understand the intrinsic nature
of these problems, discovering which are inherently feasible and which are inherently infeasible.
I will survey what is known about the complexity of counting problems, focussing especially on approximate counting.
Completely classifying
the complexity of all such problems is well
beyond the scope of what we can do today, but progress is being made
in widely-applicable domains such as counting constraint satisfaction problems
and graph homomorphism problems.