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 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


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!

Ofir


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: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20181026/fb6b756b/attachment.html>


More information about the theory-seminar mailing list