Mathematics Colloquium

An average John theorem

Speaker: Assaf Naor, Princeton University

Location: Online

Videoconference link:

Date: Monday, May 3, 2021, 3:45 p.m.


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.