Skip to content
Texas A&M University
Mathematics

Seminar on Banach and Metric Space Geometry

Date: February 28, 2020

Time: 3:00PM - 4:00PM

Location: BLOC220

Speaker: Alex Andoni, Columbia University, Data Science Institute

  

Title: Estimating distances in a graph metric, in parallel

Abstract: 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.