Assaf Naor

Assaf Naor
(Department of Mathematics, Princeton University)

Day 2 (April 15) @ 09:00 – 10:00 Keynote

Title: 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.