Chern Lecture/Mathematics Department Colloquium: An average John theorem

Colloquium | March 14 | 4:10-5 p.m. | 60 Evans Hall

 Assaf Naor, Princeton University

 Department of Mathematics

We will prove a sharp average-case variant of a classical embedding theorem of John through the theory of nonlinear spectral gaps. We will use this theorem to provide a new answer to questions of Johnson and Lindenstrauss (1983) and Bourgain (1985) on metric dimension reduction, and explain how it leads to unexpected algorithms for approximate nearest neighbor search.