Program

This MSRI special semester is dedicated to the study of geometric properties of high dimensional objects and normed spaces, and the asymptotics of their quantitative parameters as the dimension tends to infinity. Methods from the field of geometric functional analysis successfully interact with several areas including harmonic analysis, probability, random matrices, compressed sensing and convex programming. A priori, one would expect geometry in high-dimensional spaces to be rather complicated. Our experience in low dimensions seems to indicate that as the number of dimensions increases, the number of possible configurations grows rapidly, and we encounter the realm of enormous, unimaginable diversity. For instance, the classification of closed two-dimensional surfaces has been known for a long time, and a decade ago Perelman completed the proof of Thurston’s geometrization conjecture regarding the structure of closed three-dimensional manifolds. However, it is clear that the space of four-dimensional manifolds is extremely complicated; the fundamental group in four dimensions can be essentially anything. It therefore seems that a general, interesting theory, with results that are relevant to all high-dimensional objects - is impossible to attain. Nevertheless, there are occasional sparks of simplicity, order and universality in high dimensions. One of the earliest such examples is the classical central limit theorem, according to which a normalized sum of independent random variables is approximately Gaussian, under very general assumptions, when the number of variables approaches infinity. Another example is Dvoretzky’s theorem, which demonstrates that any high-dimensional convex body has nearly Euclidean sections of a high dimension. Note that the symmetries of the Euclidean ball emerge from minimal assumptions, only convexity and the high dimension. As it turns out, there are a few strong motifs in high-dimensional geometry which seem to compensate for the difficulties that arise from high dimensionality. One of these motifs is the concentration of measure phenomenon. Surprisingly, typical functions on a high dimensional space behaves in many cases as if they were constant functions. For example, if we sample five random points from the n-dimensional unit sphere, and substitute them into a 1-Lipschitz function, then we will almost certainly obtain five numbers that are very close to one another. This phenomenon is reminiscent of the geometric property that in the high-dimensional Euclidean sphere, “most of the mass is close to the equator, for any equator”. The latter property is unthinkable in, say, three dimensions. This geometric property has paved the way to a wealth of geometric inequalities and applications related to “measure concentration”, involving a wide range of techniques, from transportation of measure to the heat semigroup, and from isoperimetric inequalities to log-Sobolev inequalities. Ideas and methods of geometric functional analysis found a number of applications in computer science, especially in high-dimensional randomized algorithms. In many cases, when deterministic algorithms do not exist or are unknown, the methods relying on measure concentration provide efficient probabilistic substitutes. This is, however, a two-way street, as computer science questions have led to purely mathematical problems which are among the most important in the whole area. Bibliography (PDF)