Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Distance Computation in Distributed Networks
event speaker icon
Michal Dory, Ph.D. Thesis Seminar
event date icon
Wednesday, 24.6.2020, 14:30
event location icon
Zoom Lecture:
event speaker icon
Advisor:  Prof. Keren Censor-Hillel
In this talk, I will describe a couple of results from my PhD thesis, that studies distributed algorithms for connectivity and distance related graph problems. I will focus on a recent line of work studying distance computation in the Congested Clique model of distributed computing. We design fast algorithms for the fundamental all-pairs shortest paths (APSP) and multi-source shortest paths (MSSP) problems. In particular, we show constant-factor approximation algorithms for weighted APSP and MSSP that take just poly-logarithmic time. Moreover, in unweighted graphs, we solve the same problems much faster, in just poly(loglogn) time. All previous algorithms require at least a polynomial number of rounds. Our main techniques are new distance tools we develop, based on sparse matrix multiplication, and a new fast construction of a near-additive emulator, a sparse graph that preserves the distances of the original graph up to a near-additive stretch. Based on joint works with Keren Censor-Hillel, Janne H Korhonen, Dean Leitersdorf, and Merav Parter.
[Back to the index of events]