[theory-seminar] TCS+ talk: Wednesday, March 28, Artur Czumaj, University of Warwick

[Clément Canonne]

Hi all,

Next week, we'll be having a TCS+ talk from the comfort of Gates 463A, 
at 10am as usual (with breakfast-ey things at 9h55).

Artur Czumaj will be talking from Coventry about "Round Compression for 
Parallel Matching Algorithms," showing how to get a 2.01-approximation 
to maximum matching in the MPC model with exponentially fewer rounds 
than in the PRAM one (abstract below).

See you on Wednesday morning,

-- Clément


-------------------------------
-------------------------------
Speaker: Artur Czumaj (University of Warwick)
Title: Round Compression for Parallel Matching Algorithms

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.