Computational Counting

Lead Research Organisation: University of Leeds
Department Name: Sch of Computing

Abstract

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.

Publications

10 25 50
publication icon
Bulatov A (2012) The complexity of weighted and unweighted #CSP in Journal of Computer and System Sciences

publication icon
Chen X (2015) The complexity of approximating conservative counting CSPs in Journal of Computer and System Sciences

publication icon
Dyer M (2012) The complexity of approximating bounded-degree Boolean #CSP in Information and Computation

publication icon
Martin Edward Dyer (Co-Author) (2013) The complexity of approximating conservative counting CSPs

 
Description A decidable dichotomy theorem for counting constraint satisfaction problems.
Exploitation Route Already been used to prove an even more general theorem by Cai and Chen.
Sectors Digital/Communication/Information Technologies (including Software),Education