Institute of Information Science Academia Sinica
Topic: Efficient massively parallel graph coloring algorithms via transformations from distributed local algorithms
Speaker: Mr. Yi-Jun Chang (Department of EECS, University of Michigan)
Date: 2019-06-14 (Fri) 10:00 – 12:00
Location: Auditorium106 at IIS new Building
Host: Kai-Min Chung

Abstract:

The Massively Parallel Computation (MPC) model was introduced recently as a theoretical abstraction for practical large-scale parallel processing settings such as MapReduce, Hadoop, Spark, and Dryad, and it has been receiving increasing more attention over the past few years. In this talk, we will discuss a method for transforming distributed local algorithms into efficient parallel algorithms, and how this approach leads to efficient graph coloring algorithms in the MPC model and some other related computation models. The talk will be mainly based on this paper: https://arxiv.org/abs/1808.08419  (PODC 2019)