Special Seminar: Jara Uitto "Distributed and Massively Parallel Algorithms for Graph Problems"

Distributed and Massively Parallel Algorithms for Graph Problems

Jara Uitto

Abstract:

First, I will focus on classic message passing algorithms. In this setting, we have a network of computers that communicate via fixed communication links.The main challenge in solving graph problems is that the nodes have to base their decision on only local information about the graph. I will survey recent developments in lower bound techniques for problems such as the algorithmic Lovász Local Lemma as well as algorithmic advances on the classic edge-coloring problem.

The second setting, Massively Parallel Computation (MPC), aims to build theoretical foundations of large-scale graph processing frameworks such as MapReduce, Hadoop, Spark, etc. In the MPC model, the input size is much larger than the internal memory and the communication capacity of each single computer. Therefore, we use many computers, which communicate with each other, to solve the problem. I will introduce a technique that sparsifies the input and allows us to import message passing algorithms into the MPC model.

Bio:

Jara Uitto is currently a postdoctoral researcher affiliated with the Distributed and Discrete Algorithms group led by Prof. Mohsen Ghaffari at ETH Zurich and with the Algorithms and Complexity group led by Prof. Fabian Kuhn at University of Freiburg. He received his PhD from ETH Zurich under the supervision of Prof. Roger Wattenhofer and Prof. Yuval Emek. His main research interests lie in graph algorithms and, in particular, in the foundations of distributed and parallel computing. His recent work includes new algorithmic techniques for classic symmetry breaking problems in the Massively Parallel Computing (MPC) model and in the classic LOCAL model of distributed computing.