Nonlinear Dvoretzky Theory

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I
Topic:Nonlinear Dvoretzky Theory
Speaker:Assaf Naor
Affiliation:Courant Institute of Mathematical Sciences
Date:Monday, December 6
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/naor

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.