Plenary lecture

Day 1 (Tuesday 2 April) @ 10:15 – 11:00

Leslie Ann Goldberg (University of Oxford)

The Complexity of Approximate Counting

This talk will be a survey on the complexity of approximate counting. This is a research area that lies at the intersection of theoretical computer science, combinatorics, and probability. No special background will be required.

In theoretical computer science, the goal is to determine which computational problems have fast algorithms and which computational problems provably do not have fast algorithms. The “complexity” of a problem is a rigorous quantification of how difficult it is to solve, in terms of the existence of fast algorithms. The particular object of study here is “approximate counting” which is the study of computing certain functions called partition functions. Partition functions are relevant to spin systems such as the Ising model from statistical physics.  The basic object is a “configuration”, in which the vertices of a graph are mapped to a finite set of spins, say {0,1}. The spins interact locally along the edges of the graph, in the sense that any adjacent pair of spins gives rise to an interaction weight. The weight of the configuration is the product of these interaction weights, and the partition function is the sum of the weights of all configurations. It can be used to determine qualitative properties of the model and it is the normalising factor needed to sample configurations from the corresponding probability distribution.

I will tell you what is known about the complexity of exactly computing partition functions (which is a lot!) and about the complexity of approximately computing partition functions (which is much less, though approximation turns out to be the more natural question!). I will focus on the special   case where there are only two spins, which, perhaps surprisingly, is still not completely resolved.

I will first describe the pleasing characterisation of the case where interaction weights are non-negative real numbers which was discovered about a decade ago (by several researchers). This characterises the complexity of the approximate counting problem on general graphs in terms of the uniqueness of certain distributions on infinite trees.  

I will also tell you about key algorithms by Barvinok and by Patel and Regts, which show how to approximate certain real-valued partition functions by boot-strapping zero-free regions of these functions in the complex plane. Finally, I will tell you about some new work with Yumou Fei and Pinyan Lu on the case with (possibly negative) real interaction weights. In this work, we give some fast approximation algorithms, and we also identify regions where we can prove that fast approximation is impossible, given the usual complexity-theoretic assumptions.

Biography

Leslie Ann Goldberg is a Professor at the University of Oxford, where she is also the Head of the Department of Computer Science. Leslie’s academic interest is in the mathematical foundations of Computer Science, where the goal is to quantify the inherent complexity of computational problems, and the inherent quality of approximation algorithms (giving rigorous proofs about what is possible in terms of computation). Leslie focusses especially on the role of randomness in computation. She has received several awards for her academic work, including 5 best-paper prizes, an ERC Advanced Grant, election to  Academia Europaea, a Suffrage Science award (which “celebrates women in science for their scientific achievement and for their ability to inspire others”) and was elected as a Fellow the European Association for Theoretical Computer Science “for fundamental contributions to many areas of theoretical computer science, primarily focusing on randomized algorithms and their limitations”.