Distance Computation in Massive Graphs

(The talk will be given in English)

Speaker:     Dr. Michal Dory

Department of Computer Science, ETH Zurich

Abstract

Computing distances in a graph is one of the most fundamental problems in graph algorithms.
But how can we solve it when the input graph is too large and cannot be stored in one computer?
This type of problems are studied in the area of distributed computing. 
In this talk, I will give an overview of the area of distributed computing, with a focus on distance computation.
I will discuss a recent line of work that led to extremely fast distributed algorithms for approximating shortest paths, improving exponentially over the state-of-the-art. 

Short Bio

Michal Dory is a post-doctoral researcher at ETH Zürich. She received her PhD from the Technion in 2020. Her research interests are in distributed computing and graph algorithms. Her works received several awards, including the best paper award in PODC 2020, the best student paper award in PODC 2019, the best paper award in OPODIS 2017, and the Technion's Jacobs Prize for an excellent publication in 2019.