Colloquium Dvoretzky lecture: Assaf Naor(Princeton) - An average John theorem

Thu, 27/06/201914:30-15:30
Manchester Building (Hall 2), Hebrew University Jerusalem

Abstract: 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 algorithms for approximate nearest neighbor search.