Chern Lecture/Mathematics Department Colloquium: An average John theorem
Colloquium | March 14 | 4:10-5 p.m. | 60 Evans Hall
Assaf Naor, Princeton University
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.