Mapping the Complexity of Counting

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:

• To map out the landscape of computational counting problems (exact and approximate), determining which problems are tractable and which are intractable (quantifying the extent of tractability), and
• To develop complexity characterisations elucidating the features that make counting problems tractable or intractable (so the goal is not only to discover which problems are tractable, but also to discover a characterisation which tells us why).