In solidarity with the current protests in the United States (https://www.shutdownstem.com/), our speaker asked that the talk this coming Wednesday be postponed.
Cliff’s talk has been rescheduled to Thursday, June 18th; we will keep you updated in case of any further change. We would also take this opportunity to call the TCS community for feedback, and for suggestions and comments. As a small team organizing this virtual seminar, we are continuously trying to improve and welcome your input.
The next TCS+ talk (and the last of the season!) will take place this coming Wednesday, June 10th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Cliff Stein from Columbia University will speak about “Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators” (abstract below).
You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The link to the YouTube livestream will also be posted on our
website on the day of the talk, so people who did not sign up will still be able to watch the talk live.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see >the website.
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 -approximate parallel algorithm for computing shortest paths in undirected graphs, achieving polylog depth and near-linear work. All prior -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.