Mohsen Ghaffari: Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Friday, April 13, 2018 - 1:00pm to 2:30pm
Refreshments:
Lunch at 12:30pm
Location:
32-G5th floor lounge
Speaker:
Mohsen Ghaffari
Biography:
ETH-Zurich
Seminar group:
In this white-board talk, I will explain some new Massively Parallel Computation (MPC) algorithms for graph problems such as approximating maximum matching and minimum vertex cover. These algorithms improve on the round complexity of the previously known algorithms and are also considerably simpler.
Based on a joint work with Gouleakis, Mitrovic, and Rubinfeld, which can be found on arXiv:1802.08237.