Lecture 1. Introduction

Computing, or at least estimating, the volume of a body is one of the oldest questions in mathematics, studied already in Egypt and continued by Euclid and Archimedes. Here we are mostly concerned with the computational complexity of estimating volumes of convex bodies in ℝn, with n large. The problems and results to be discussed are all rather recent, most of them less than ten years old, and although there was a breakthrough a few years ago and by now there are several substantial and exciting results, there is much to be done.

In vague terms, we would like to find a fast algorithm that computes, for each convex body K in ℝn, positive numbers vol K and vol K such that and vol K/vol K is as small as possible.

This formulation has several flaws. It is not clear what our algorithm is allowed to do and how its speed is measured; we also have to decide how our convex body is given and how small vol K/vol K we wish to make. Our first aim is then to make this problem precise.

If there is no danger of confusion, we write volK for the volume of a body K, in whatever the appropriate dimension is; if we want to draw attention to the dimension we write vol& L for the /c-dimensional volume of a k-dimensional body L.

By a convex body in ℝn we mean a compact convex subset of ℝn, with nonempty interior.