I will show how to build efficient nearest neighbor search data structures for general metric spaces using a novel randomized partitioning procedure which is closely related to metric spectral gaps. Based on joint work with Alex Andoni, Assaf Naor, Sasho Nikolov and Erik Waingarten.

We show how to estimate distances (and shortest paths) between nodes in undirected graphs using a fast parallel algorithm. Our algorithm achieves $(1+\epsilon)$ approximation, poly(log n) time and m*poly(log n) work for n-nodes m-edges graphs --- a question open since Cohen's result from STOC'94. One of our main tools is a new notion of low hop emulators: a poly(log n)-approximate emulator graph in which every shortest path has at most O(loglog n) hops (edges). Direct applications of this tool are efficient parallel constructions of Bourgain's embedding, metric tree embedding, and low diameter decomposition. To obtain the better approximation ratio, we introduce compressible preconditioners and apply it inside Sherman's framework (SODA'17) to solve the more general problem of transportation in graphs (uncapacitated minimum cost flow). As a consequence, it also improves the state-of-the-art sequential running time for the latter. Joint work with Cliff Stein, Peilin Zhong. To appear in STOC'20.