Computer Science/Discrete Mathematics Seminar I

The classical Dvoretzky theorem asserts that for every integer k>1 and every target distortion D>1 there exists an integer n=n(k,D) such that any n-dimensional normed space contains a subspace of dimension k that embeds into Hilbert space with distortion D . Variants of this phenomenon for general metric spaces have been studied for 25 years, with a variety of applications. In this talk we will discuss the solution of the nonlinear Dvoretzky problem of Bourgain-Figiel-Milman, as well as more recent work on Tao's Dvoretzky problem for Hausdorff dimension. A sample result along these lines (obtained jointly with Manor Mendel) is that for every epsilon > 0 , any n-point metric space has a subset of size n^{1-epsilon} which embeds into Hilbert space with distortion O(1/epsilon) ; a result that is optimal up to constant factors. We will also describe subtle connections between nonlinear Dvoretzky theory and theoretical computer science, as well as the appearance of a variety of probabilistic tools in the study of such problems, including random walks on metric spaces and randomized Calderon-Zygmund decompositions.