Abstract

For nearly two decades now we have been witnessing the success of frameworks for parallel computation, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to PRAM, these frameworks allow for much more local computation.

The Massively Parallel Computation (MPC) model is a de facto standard for abstracting out capabilities of these frameworks. Over the last couple of years, MPC has received significant attention, most notably in the context of graph algorithms. In this talk, I will describe three popular MPC techniques that proved to be successful for obtaining efficient algorithms for a number of fundamental graph theoretical problems. Then I will focus on the task of approximating maximum matchings, and show how some of those techniques can be used to obtain algorithms that are exponentially faster than the state-of-the-art algorithms designed for PRAM.

Bio

Slobodan is a postdoctoral fellow at MIT hosted by Prof. Ronitt Rubinfeld. Prior to coming to MIT, he spent two months at ETH visiting Prof. Mohsen Ghaffari. He received a Master’s and a PhD degree from the Computer Science department at EPFL. His PhD advisor was Prof. Aleksander Mądry.

Broadly speaking, Slobodan’s research spans the areas of graph theory and algorithmic approach to optimization. He has worked on graph algorithms for models of parallel computation; space-efficient algorithms for submodular maximization; and combinatorial optimization in the context of randomized routing and compressive sensing.

Host

Assistant Professor Jara Uitto, Aalto University Department of Computer Science