skip to main content

TCS+ Talk

Wednesday, March 28, 2018
10:00am to 11:00am
Add to Cal
Annenberg 205
Round Compression for Parallel Matching Algorithms
Artur Czumaj, University of Warwick,

Abtract:  Abstract: For over a decade now we have been witnessing the success of massive    parallel computation (MPC) frameworks, such as MapReduce, Hadoop,    Dryad, or Spark. One of the reasons for their success is the fact    that these frameworks are able to accurately capture the nature of    large-scale computation. In particular, compared to the classic    distributed algorithms or PRAM models, these frameworks allow for    much more local computation. The fundamental question that arises in    this context is though: can we leverage this additional power to    obtain even faster parallel algorithms?
A prominent example here is the fundamental graph problem of finding    maximum matching. It is well known that in the PRAM model one can    compute a 2-approximate maximum matching in O(log n) rounds.    However, the exact complexity of this problem in the MPC framework    is still far from understood. Lattanzi et al. showed that if each    machine has n^{1+Ω(1)} memory, this problem can also be solved    2-approximately in a constant number of rounds. These techniques, as    well as the approaches developed in the follow up work, seem though    to get stuck in a fundamental way at roughly O(log n) rounds once we    enter the near-linear memory regime. It is thus entirely possible    that in this regime, which captures in particular the case of sparse    graph computations, the best MPC round complexity matches what one    can already get in the PRAM model, without the need to take    advantage of the extra local computation power.
In this talk, we finally show how to refute that perplexing    possibility. That is, we break the above O(log n) round complexity    bound even in the case of slightly sublinear memory per machine. In    fact, our improvement here is almost exponential: we are able to    deliver a (2+ϵ) approximation to maximum matching, for any fixed    constant ϵ>0, in O((loglog n)^2) rounds.
This is a joint work with Jakub Łącki, Aleksander Mądry, Slobodan    Mitrović, Krzysztof Onak, and Piotr Sankowski.

For more information, please contact Bonnie Leung by email at [email protected].