Theory Lunch Seminar

  • Ph.D. Student
  • Department of Computer Science
  • Columbia University

Approximate Nearest Neighbors via Non-Linear Spectral Gaps

I will present recent advances in approximate nearest neighbor search data structures for general normed spaces. I will explain what non-linear spectral gaps are, and how to use estimates on non-linear spectral gaps to partition large graphs whose vertices lie in a normed space. The main result is a data structure for approximate near neighbors in any norm with sub-polynomial approximation im the dimension.

Based on joint work with Alex Andoni, Assaf Naor, Sasho Nikolov, and Ilya Razenshteyn.

CMU Youtube Theory channel

For More Information, Please Contact: