The Complexity of Counting Problems
David Richerby
Abstract: Every computational decision problem ("Is there an X?") has a natural counting variant ("How many X's are there?"). More generally, computing weighted sums such as integrals, expectations and partition functions in statistical physics can also be seen as counting problems.
This tutorial will give an introduction to the complexity of solving counting problems, both exactly and approximately. I will focus on variants of constraint satisfaction problems. These are powerful enough to naturally express many important problems, but also being restricted enough to allow their computational complexity to be classified completely and elegantly. No prior knowledge of counting problems will be assumed.
Bio: David Richerby is a lecturer in computer science at the University of Essex, in Colchester, UK. His main areas of research are the computational complexity of counting problems, stochastic processes on graphs, and the summarization of large graph databases. He is particularly interested in variants of the constraint satisfaction problem and homomorphism problems and he is a joint winner of the 2021 SIGACT/EATCS Goedel Prize for his contributions in this area. David has previously worked at the Universities of Cambridge, where he obtained his PhD in logic and descriptive complexity, Athens, Leeds, Liverpool and Oxford.
