Mapping the Complexity of Counting (MCC)

This project is funded by an ERC Advanced Grant. The project ran from 1 March 2014 through 31 Aug 2019 in the Department of Computer Science at the University of Oxford.

Principal Investigator

Postdoctoral Research Fellows

DPhil Students

Faculty Collaborators

Past Members

Project Summary:

Just as advances in engineering rely on a deep foundational knowledge of physics, so too advances in algorithms and programming rely on a deep knowledge of the intrinsic nature of computation. Significant progress has been made in understanding the nature of computation, particularly in the field of computational complexity, which aims to discover which computational problems are feasible and which are inherently infeasible (and why). However, huge theoretical challenges remain: many classes of problems are poorly understood, including those containing problems arising in practical applications.

The MCC project will enable significant computational advances in a host of application areas through the development of a comprehensive theory of counting problems. These problems are common and important: they arise in practical applications from diverse fields including statistics, statistical physics, information theory, 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. Since these counting problems arise in applications everywhere, it is of fundamental importance to understand their complexity.

We propose a coherent and systematic study of the complexity of counting problems. The overall objectives of the project are:

Visitors

Funding information

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007--2013) ERC grant agreement no. 334828. Our papers and publicity reflect only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

Papers