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