Parallel approximate undirected shortest paths via low hop emulators
Clifford Stein (Coumbia University)
Abstract: Although sequential algorithms with (nearly) optimal running time for finding shortest paths in undirected graphs with non-negative edge weights have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. In this talk, we present a $(1+\varepsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving polylog depth and near-linear work. All prior $(1+\varepsilon)$-algorithms with polylog depth perform at least superlinear work. Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for 25 years.
Our algorithm uses several new tools. Prior work uses hopsets to introduce shortcuts in the graph. We introduce a new notion that we call low hop emulators. We also introduce compressible preconditioners, which we use in conjunction with Serman's framework (SODA '17) for the uncapacitated minimum cost flow problem.
Joint work with Alex Andoni and Peilin Zhong.
distributed, parallel, and cluster computingdiscrete mathematicsdata structures and algorithmscombinatoricsinformation theoryoptimization and controlprobability
Audience: researchers in the topic
Comments: Rescheduled to 06/18/2020 (originally scheduled for the 06/10/2020).
Series comments: Description: Theoretical Computer Science
People can register to a talk via our webpage sites.google.com/site/plustcs/livetalk , or subscribe to our calendar and mailing list at sites.google.com/site/plustcs/rss-feeds
| Organizers: | Clément Canonne*, Anindya De, Sumegha Garg, Gautam Kamath, Ilya Razenshteyn, Oded Regev, Tselil Schramm, Thomas Vidick, Erik Waingarten |
| *contact for this listing |