This EPSRC-funded research project (EP/I011528/1, EP/I011935/1, EP/I012087/1, runs from 01 March 2011 to 28 February 2014.

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.

• Martin Dyer, School of Computing, University of Leeds,
• Leslie Ann Goldberg, Department of Computer Science, University of Liverpool,
• Mark Jerrum, School of Mathematical Sciences, Queen Mary, University of London.

• David Richerby, Department of Computer Science, University of Liverpool,
• Paidi Creed School of Mathematical Sciences, Queen Mary, University of London.

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.