Speaker: Erik Waingarten, Columbia University
Title: Approximate Near Neighbors for General Symmetric Norms
I will show an efficient approximate nearest neighbor search (ANN) algorithm over an arbitrary high-dimensional *symmetric* norm. Traditionally, the ANN problem in high dimensions has been studied over the Manhattan and Euclidean distances with a few exceptions. Thus, this new result is a (modest) step towards a unified theory of similarity search. At a very high level, the algorithm proceeds by embedding a symmetric norm into a carefully crafted product space, which we can handle via a combination of classical and new tools. The resulting data structure achieves doubly-logarithmic approximation using sub-polynomial query time and near-linear space. Joint work with Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, and Ilya Razenshteyn.
Erik Waingarten is a second-year PhD student at Columbia University advised by Xi Chen and Rocco Servedio. He is broadly interested in algorithms and complexity, and much of his recent work has focused on property testing, as well as algorithms for high-dimensional geometry. Before joining Columbia, he did his undergraduate studies in mathematics at MIT.