# Computational Counting

Lead Research Organisation:
University of Liverpool

Department Name: Computer Science

### 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.

### Planned Impact

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.

## People |
## ORCID iD |

Leslie Ann Goldberg (Principal Investigator) |

### Publications

Goldberg L
(2012)

*A counterexample to rapid mixing of the Ge-Štefankovic process*in Electronic Communications in Probability
Goldberg L
(2013)

*A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid*in SIAM Journal on Computing
Doerr B
(2011)

*Adaptive Drift Analysis*in Algorithmica
Díaz J
(2012)

*Approximating Fixation Probabilities in the Generalized Moran Process*in Algorithmica
Goldberg L
(2012)

*Approximating the partition function of the ferromagnetic Potts model*in Journal of the ACM
Goldberg L
(2013)

*Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials*in Journal of Computer and System Sciences
Goldberg L
(2011)

*Automata, Languages and Programming*
Goldberg L
(2012)

*Automata, Languages, and Programming*
Goldberg L
(2012)

*Inapproximability of the Tutte polynomial of a planar graph*in computational complexity
Díaz J
(2013)

*On the fixation probability of superstars*in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Chebolu P
(2012)

*The complexity of approximately counting stable roommate assignments*in Journal of Computer and System Sciences
Dyer M
(2012)

*The complexity of approximating bounded-degree Boolean #CSP*in Information and Computation
Göbel A
(2014)

*The complexity of counting homomorphisms to cactus graphs modulo 2*in ACM Transactions on Computation Theory
Bulatov A
(2013)

*The expressibility of functions on the boolean domain, with applications to counting CSPs*in Journal of the ACM### Related Projects

Project Reference | Relationship | Related To | Start | End | Award Value |
---|---|---|---|---|---|

EP/I011528/1 | 01/03/2011 | 30/06/2013 | £327,205 | ||

EP/I011528/2 | Transfer | EP/I011528/1 | 01/07/2013 | 28/02/2014 | £88,031 |

Description | This grant finished before ResearchFish was introduced, but it resulted in many results about the complexity of computational counting. These were published in 18 papers, 16 of which are listed against part 1 of the grant, and 2 of which are listed against part 2 (the new grant number was issued becaused I moved from Liverpool to Oxford). |

Exploitation Route | The research findings are relevant to researchers in algorithms and complexity and also to people who use counting algorithms, for example in statistics and statistical physics |

Sectors | Digital/Communication/Information Technologies (including Software),Education |

Description | In the project we made many discoveries about the complexity of counting. These were used by other researchers in algorithms and complexity. |

First Year Of Impact | 2012 |

Sector | Other |