Seminar Details

Locality Sensitive Hashing (LSH) is one of the most popular techniques for the problem of approximate nearest neighbor search in high-dimensional spaces. The quality of LSH is characterized by how small its parameter $\rho$ can achieve as a function of the approximation factor $c$. While tight bounds for $\rho$ are established for several metric spaces, such as Hamming, Euclidean, and spherical geometries, the algorithmic landscape for hyperbolic space $\mathbb{H}^d$ remains largely unexplored. In this work, we present the first LSH construction native to hyperbolic space. I will also mention a JL-type dimension reduction result in hyperbolic space. We will have a longer discussion on open problems.