The Taub Faculty of Computer Science Events and Talks

We show extremely efficient distributed algorithms for sparse matrix multiplication, distance computations (e.g. All-Pairs-Shortest-Paths, APSP), and subgraph existence problems. Our work identifies core observations regarding distributed computation and uses these to simultaneously tackle a variety of problems in several theoretical, distributed models. The central theme uniting our developments is designing sparsity-aware load balancing techniques and then applying them to problems on general, non-sparse, graphs.