Computational Counting

Computational complexity is typically concerned with decision problems, but this is a historical accident, arising from the origins of theoretical computer science within logic. Computing applications, on the other hand, typically involve the calculation of numerical quantities. These applications broadly fall into two types: optimisation problems, in which the goal is to maximise or (minimise) the value of a function, and counting problems, broadly interpreted, by which we mean computing sums, weighted sums, and integrals including, for example, the expectation of a random variable or the probability of an event.

This project will consider all aspects of computational counting, with a particular focus on foundational questions in computational complexity (characterising the inherent difficulty of problems) and the development of algorithmic techniques.

The goal of the project is to provide a better understanding of the inherent computational difficulty of counting (including approximate counting) and to provide efficient algorithms where they exist.