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


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.

Date: 

Thu, 27/06/2019 - 14:30 to 15:30

Location: 

Manchester Building (Hall 2), Hebrew University Jerusalem