The Taub Faculty of Computer Science Events and Talks

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.