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.

The impact of the project derives from the importance of computational counting -- real-world computing typically involves the computation of numerical quantities through weighted counting , which is also called multivariate integration . The complexity of multivariate integration is clearly of central interest in the wider field of scientific computation. Understanding the computational foundations of this subject is crucial for its development. Our main approach to communicating our discoveries will be through high-quality publications in the scientific literature and dissemination at internationally-leading conferences in the area. This includes publication of results in computer-science journals of the highest quality, presentation of our results at top-rated international computer science conferences, early dissemination of all of our work on the computer science ArXiv, and presentation of our work in venues where researchers from application areas such as statistical physics and constraint satisfaction are present. See our Pathways to Impact document for details, examples, and our recent track-record on this kind of dissemination. Dissemination, communication, and collaboration are important aspects of the project, and this is why we have chosen to begin the project with a special Dagstuhl seminar devoted specifically to the topic of this project. This seminar, co-organised by Goldberg and Jerrum, together with Burgisser, is entitled Computational Counting . It will take place in December 2010, and will enable us to build a network of researchers interested in all aspects of computational counting. The work will also form one of the themes of a further Dagstuhl seminar Design and Analysis of Randomized and Approximation Algorithms , in June 2011, co-organised by Dyer, together with Feige, Frieze and Karpinski. Computational counting is less well understood than other aspects of computational complexity theory. One of the reasons for this is the lack of textbooks in the area. In order to address this deficiency, we will consider, towards the end of the project, undertaking the production of a textbook/research monograph. We are not proposing this textbook as a direct outcome of the project. Rather, at the end of the project, when we know as much as possible about computational counting (and once we have advanced this knowledge as much as we can) it will be an appropriate time to consider writing a textbook directed at a wider audience. Note that the ultimate beneficiaries of this research (and indeed, of all research within computational complexity) are users of computers. The main goal of this work is to improve our understanding of computational problems and their complexity. Improved understanding leads to improved algorithms, and ultimately, to improved software. Equally importantly, better understanding provides warnings of problem areas where fast algorithms cannot be expected. An important sub-goal of the project is the training of first-rate new researchers in Algorithms and Complexity (our PDRAs). These young people will help the development of the field within the UK, and further enhance its reputation. It is likely (given the short supply within the UK) that the PDRAs will be recruited from outside of the UK. This will have the additional benefit of bringing excellent researchers into the country. The range of leading international collaborators on the project will also create impact. We are anticipating visitors from the USA, Canada and China as part of the project, and we will make reciprocal visits. Beyond the identifiable beneficiaries of the project there may well be unanticipated ones. Fundamental algorithmic research which was undertaken with the aim of understanding computation has contributed enormously to technological progress in recent years, as Goldreich and Wigderson have observed. It will be a welcome bonus if our work produces such benefits.