Past lectures

Abstract

At the outset, the field of computational complexity focused on decision problems and was successful in illuminating the links between computation and logic. The desire to extend the reach of the subject beyond logic and into mathematics in general has led to many new and interesting developments. That this should happen was almost inevitable: much of mathematics is concerned with quantification, a notion that does not fit well into the classical formulation of computational complexity in terms of decision problems. As a result of recent developments, it is possible to treat problems of quantification - enumeration, integration, etc. - in a reasonably coherent and illuminating manner, and that will be the aim of this course. It transpires that these problems have a different nature from decision problems, and their study requires different methods.

The following (non-exhaustive) list provides an indication of topics to be covered. Classical algorithms in combinatorial enumeration, evidence for intractability, Valiant's class #P; computational intractability of problems when instances are drawn at random; structural complexity: relationship of #P to other complexity classes, including Toda's theorem. The relationship between approximate counting and sampling: sampling via Markov chain simulation; analytical tools for estimating rates of convergence to equilibrium of Markov chains: coupling, Poincaré and "conductance" bounds; slow convergence and its relationship to "phase transitions". Other approaches: Karp-Luby (cardinality of a union of sets), Godsil-Gutman and Barvinok (permanent of a matrix). Non-approximability results.