אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Given a distributed network, represented by a graph of computation nodes connected by communication edges, a fundamental problem is computing distances between nodes. Our recent line of works show that while exactly computing all distances (All-Pairs-Shortest-Paths, APSP) in certain distributed settings currently has O(n^{1/3}) complexity, it is possible to find very good distance approximations even with an O(1) complexity. This talk will present a unified view of our various papers developing these interesting advances in distributed computing. The central theme uniting these developments is designing sparsity-aware algorithms, and then applying them to problems on general, non-sparse, graphs. Primarily, the main tools used are a series of distributed sparse matrix multiplication algorithms we develop. We then use these tools in novel manners to develop a toolkit for basic distance computations, such as computing for each node the distances to the O(n^{2/3}) nodes closest to it. Next, we use these tools to solve end-goal distance problems, in O(log^2 n) rounds. Subsequently, we adapt the load-balancing techniques used in the matrix multiplication algorithms to show combinatorial algorithms which directly compute APSP approximations, without passing through other intermediate distance tools. This allows us to show O(1) round algorithms. Finally, the talk concludes with observing the connection of the above addressed works to other developments in the realm of distributed computing, specifically MST computation and subgraph existence problems.