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

[Clément Canonne]

Reminder: this is tomorrow (morning)!

-- Clément

On 03/22/2018 04:18 AM, Clément Canonne wrote:
> 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.