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

[Ofir Geri]

Correction: The talk will take place in Gates 104.

________________________________
From: Ofir Geri
Sent: Friday, October 26, 2018 11:08:44 AM
To: thseminar at cs.stanford.edu
Subject: Re: Theory Seminar (10/26): Erik Waingarten


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/e4dee37a/attachment.html>