Mathematics Colloquium

A classical theorem of Fritz John implies that any n-dimensional normed space embeds with distortion \sqrt{n} into a Hilbert space. This bound is sharp, but can we do better if we relax the worst-case bi-Lipschitz requirement by asking for distances to be preserved only on average? We will show that a suitable formulation of this question has a positive answer whose proof borrows from the theory of nonlinear spectral gaps. Specifically, we will show that the average distortion decreases in general to O(\sqrt{\log n}), and under additional geometric assumptions even better bounds are possible. We will explain applications of this theorem to major questions in metric geometry and algorithms.