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
Fri Oct 26 15:01:02 PDT 2018

Correction: The talk will take place in Gates 104.

From: Ofir Geri
Sent: Friday, October 26, 2018 11:08:44 AM
To: thseminar at
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
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!


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