Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Seminar (10/26): Erik Waingarten

Ofir Geri ofirgeri at
Tue Oct 23 13:23:40 PDT 2018

Hi all,

This Friday at theory seminar, Erik Waingarten from Columbia will be giving a talk on Approximate Nearest Neighbors via Non-Linear Spectral Gaps (see abstract below). The talk will be as usual on Friday 3pm in Gates 463A.

Please note that we also have a theory seminar today.

Hope to see you there!


Approximate Nearest Neighbors via Non-Linear Spectral Gaps
Speaker: Erik Waingarten (Columbia)

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. As a result, I will present the first sub-linear time data structure for approximate nearest neighbor search in high-dimensional normed spaces with approximation which is sub-polynomial in the dimension.

Based on joint work with Alex Andoni, Assaf Naor, Sasho Nikolov, and Ilya Razenshteyn.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list