Massively parallel algorithms for finding connected components

Speaker(s)

Jakub Łącki

Affiliation

Google Research NY

Date

Dec. 19, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---