Dean Leitersdorf, Ph.D. Thesis Seminar
Tuesday, 7.12.2021, 12:30
Advisor: Prof. Keren Censor-Hillel
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.