Search Mailing List Archives
[theory-seminar] TCS+ talk: Wednesday, March 28, Artur Czumaj, University of Warwick
Clément Canonne
ccanonne at cs.stanford.edu
Tue Mar 27 09:39:43 PDT 2018
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.
More information about the theory-seminar
mailing list