BARC talk by Jakub Łącki

Massively Parallel Algorithms for Finding Connected Components

In this talk, we consider the problem of finding connected components in a distributed setting. We present state of the art algorithms that achieve near-optimal round complexity and work well in practice. Our main focus is the Massively Parallel Computation (MPC) model, which is the standard theoretical model for modern parallel frameworks such as MapReduce, Hadoop, or Spark.

This is joint work with Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Vahab Mirrokni, Warren Schudy and Michał Włodarczyk.

Jakub Łącki is research scientist at Google Research in New York. In 2015 he got his PhD from University of Warsaw advised by Piotr Sankowski, and from September 2015 to October 2016 he was postdoc at Sapienza University of Rome, working with Stefano Leonardi. Read more about Jakub here.