EECS Special Seminar: Mohsen Ghaffari: "Distributed Derandomization, Massively Parallel Graph Algorithms, and Beyond"

Speaker: Mohsen Ghaffari , ETH Zurich

Date: Tuesday, March 16, 2021

Time: 12:00 PM to 1:00 PM Note: all times are in the Eastern Time Zone

Public: No

Location: Virtual - TBD

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan and Virginia Williams, CSAIL MIT

Contact: Sally O. Lee, 3-6837,

Relevant URL:

Speaker URL: None

Speaker Photo:
Mohsen ghaffari

Reminders to:

Reminder Subject: TALK: EECS Special Seminar: Mohsen Ghaffari: "Distributed Derandomization, Massively Parallel Graph Algorithms, and Beyond"

Abstract: With the rapid increase in data sizes and the prevalence of decentralized systems, the computational world is constantly moving toward distributed and parallel computations. This talk overviews some of the recent highlights in distributed and massively parallel algorithms. It also outlines how some of the fundamental concepts transcend these areas, e.g., having implications in sublinear-time algorithms.

The first part of the talk describes a general and efficient derandomization result for distributed graph algorithms. This result breaks the 30-year old near-exponential gap between deterministic and randomized distributed algorithms, and leads to significant improvements in deterministic and, perhaps surprisingly, randomized distributed algorithms for several well-studied graph problems. It thereby resolves some of the area's most well-known open problems, including Linial’s 1987 MIS question.

The second part discusses a program of building bidirectional connections between massively parallel algorithms (a la MapReduce) and local distributed algorithms. This connection, along with novel sparsification techniques, gives a systematic approach for developing efficient massively parallel graph algorithms. It also leads to strong (conditional) lower bounds for massively parallel computation.

Bio: Mohsen Ghaffari is currently an Assistant Professor in the Computer Science department of ETH Zurich. He received his PhD from MIT in 2016. Mohsen's work on distributed and parallel algorithms has been recognized by eight best (student) paper awards at conferences such as SODA, PODC, ICALP, and DISC, as well as the 2017 ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award and an honorable mention of the 2017 ACM Doctoral Dissertation Award. He is also the recipient of a 2019 Starting Grant (1.5 million Euros) from the European Research Council.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Sally O. Lee Email at Wednesday, February 17, 2021 at 11:17 AM.