Mathematics Colloquium

An average John theorem

Speaker: Assaf Naor, Princeton University

Location: Online

Videoconference link: https://nyu.zoom.us/rec/share/oQICrvmrogyeh_c8wpT3lcEY8I8wzvIYN9V7nYwkI6K9-YfXmFmdmZztmYtVyk3j.F2jwyqXTFdcHqble

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

Synopsis:

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.