Assaf Naor (Princeton University)
An average John theorem
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 (pairwise) 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.
