Milner Lecture: Mark Jerrum

Milner Lectures

The Milner Lecture was endowed by the late and much-missed Robin Milner when he left Edinburgh for Cambridge, and is for a public lecture by someone outside Edinburgh who is doing "excellent theoretical work with a perceived application to practice". In this year of celebration, our speakers are asked to set their work in the context of the history of theoretical computer science at Edinburgh.

As part of the celebrations of 60 years of Computer Science and Artificial Intelligence at Edinburgh, the Laboratory for Foundations of Computer Science held a special series of three Milner Lectures given by former members of LFCS.

Title: The computation complexity of counting problems: a personal perspective

Lecture abstract

Deciding on Edinburgh as the place to study for a PhD was indeed a fortuitous choice in 1978. The theory of NP-completeness for decision problems had been introduced seven or so years earlier. Leslie Valiant was now initiating the study of the complexity theory of counting problems, introducing a counting analogue, #P, of NP. Early on, Valiant had shown that the permanent of a 0,1-matrix (syntactically similar to the determinant, but with all terms having positive sign) is complete for the complexity class #P, and hence computationally intractable, assuming P ≠ #P. Valiant asked whether the permanent is efficiently approximable within specified relative error. This must have been a great question, as it kept some of us busy for the next two decades! More generally, the complexity of counting problems has remained a fruitful line of study for 45 years now, and is currently in one of its periodic bursts of intense activity. Gaining motivation and ideas from theoretical computer science, probability theory, statistical physics and combinatorics, this field of study is remarkably interdisciplinary. I'll aim to convey the flavour of this research area, what is known, and what we would like to know.

Speaker's bio

Mark Jerrum commenced postgraduate studies at Edinburgh University in 1978, in what was then the Department of Computer Science. Guided by Leslie Valiant, he graduated with a PhD in 1981. Like many people, he became attached to the city, and remained in the department, rising through the ranks, until leaving for London in 2006. Since then, he has worked in the School of Mathematical Sciences at Queen Mary, University of London. The formative years at Edinburgh provided a wonderful foundation for his subsequent research career. The common theme all along has been the study of the computational complexity of counting problems, including weighted counting problems as exemplified by partition functions (in physics) and generating functions (in combinatorics). Far from being restrictive, this research theme has allowed (indeed, compelled) him to explore topics in combinatorics, stochastic processes, and statistical physics, in addition to theoretical computer science. Models in statistical physics, constraint satisfaction problems and graph polynomials provide a rich source of motivating examples. He enjoys making use of what London has to offer, but also escaping for walks away from the city.