Abstract
In this talk we will mainly focus on the maximal matching problem in the Massively Parallel Computations (MPC) model. The MPC model provides a clean theoretical abstraction of modern parallel computation frameworks such as MapReduce, Hadoop, Spark, etc., which have been extremely successful in processing large-scale data-sets.
We give an outline of the analysis of an extremely simple algorithm and show that it exponentially improves over previous results for maximal matching. The analysis is based on a novel method of proving concentration bounds for algorithms satisfying a certain "locality" property, which we believe may find applications beyond the MPC model.
Based on a joint work with Mohammad Hajiaghayi and David Harris (FOCS 2019).