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

The Taub Faculty of Computer Science Events and Talks

Fast Distributed Algorithms via Sparsity Awareness
event speaker icon
Dean Leitersdorf (Ph.D. Thesis Seminar)
event date icon
Tuesday, 07.12.2021, 12:30
event location icon
Zoom Lecture: 97497750707
event speaker icon
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.