Modern Parallel Algorithms
Artur Czumaj (University of Warwick).
Course Summary |
About the lecturer |
Location and schedule |
Course materials
In this lecture series we will consider some of the recent advances in the design and analysis of "modern" parallel algorithms. For over a decade now we have been witnessing the success of massive parallel computation 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?
We will address this question in the setting of the Massively Parallel Computation (MPC) model, which is an emerging model which distills core aspects of parallel and distributed computation. The MPC model has been developed as a tool to solve (typically graph) problems in systems where the input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear memory. This course will introduce this model and will present some recent advances for fundamental problems in this area, with the focus on graph problems.
About the lecturer:Artur Czumaj is a Professor of Computer Science and Director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick. He received his PhD and Habilitation degree from the University of Paderborn in Germany. His main research interest is in the design of randomized algorithms and their probabilistic analysis, with applications to property testing and sublinear algorithms, optimization algorithms, parallel and distributed computing, string matching, and algorithmic game theory.
Slides: Lecture 1 Lecture 2 Lecture 3 HomeworkLocation and schedule:
|
|
|
||||||||||||||||