2019
Jun
27

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

2:30pm to 3:30pm

## Location:

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.