Open Lecture — The Complexity of Computing Quantities

Computability theory, as developed most notably by Turing, is a successful mathematical theory of the limits of what can be computed. Perhaps remarkably, it does not significantly involve quantities. Theories similarly light on quantitative analysis have also been provided for important issues in the complexity of computation, such as NP-completeness. However, there remain wide areas of computation, such as the evaluation of probabilities, multivariate integration, and the counting of discrete structures, where the objects to be manipulated are inherently quantitative. In this talk we shall focus on this area, in which computational complexity becomes inseparable from quantitative concerns. We highlight counting problems, in which one seeks to compute the number of discrete objects of a certain kind. The number may be exponentially large compared to the size of the objects allowed, but can be written down as a polynomial number of digits. We shall review recent progress that makes it possible to classify a wide range of such counting problems, both exact and approximate, according to their computational difficulty. This classification is sometimes offered in the strong sense of a dichotomy theorem, which classifies according to difficulty not just a single problem but a whole class. Proofs of such theorems exploit a variety of techniques, including holographic transformations.

Light refreshments will be served before the lecture at 3:30 p.m.