Michal Dory, Ph.D. Thesis Seminar
Wednesday, 24.6.2020, 14:30
Zoom Lecture: https://technion.zoom.us/j/99489358773
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.