Search Mailing List Archives
[theory-seminar] Theory Seminar (10/26): Erik Waingarten
ofirgeri at stanford.edu
Fri Oct 26 11:08:44 PDT 2018
Reminder: theory seminar is today at 3pm.
From: Ofir Geri
Sent: Tuesday, October 23, 2018 1:23:40 PM
To: thseminar at cs.stanford.edu
Subject: Theory Seminar (10/26): Erik Waingarten
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...
More information about the theory-seminar