דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Fast Approximate Shortest Paths in the Congested Clique
event speaker icon
מיכל דורי (מדעי המחשב, טכניון)
event date icon
יום רביעי, 29.5.2019, 12:30
event location icon
טאוב 201
I will discuss our recent shortest paths algorithms in the distributed congested clique model. Our first contribution is a (2+epsilon)-approximation algorithm for all-pairs shortest paths (APSP) requiring only polylogarithmic number of rounds. This is the first sub-polynomial constant approximation for APSP in this model. We also significantly improve upon the state-of-the-art for approximate multi-source shortest paths and diameter, as well as exact single-source shortest paths (SSSP). Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication.

Joint work with Keren Censor-Hillel, Janne H. Korhonen and Dean Leitersdorf.
[בחזרה לאינדקס האירועים]