Uni-Logo
Algorithms and Complexity
 

Algorithms and Complexity Seminar
Summer Term 2026

 


Seminar topic: Massively Parallel Computation Algorithms

Nowadays, there are many applications that require computations with of vast amounts of data. In such cases, the data cannot be stored and processed on a single computer. In order to simplify the development of parallel algorithms for computations in large clusters of computers, programming frameworks such as MapReduce have been developed first by industry and then also by academia. As a result of this, researchers have developed the so-called Massively Parallel Computation (MPC) model as an abstract theoretical model that allows to develop and analyze algorithms frameworks such as MapReduce. In this seminar, we will look at the most important theoretical literature on algorithms for the MPC model.

Seminar description

To pass the seminar, the students participating in the seminar have to present a research paper (the list of possible papers will soon be published on this webpage). Depending on the number of students participating in the seminar, each paper will have to be prepared and presented by a pair of students. The presentations about each paper will be 45 minutes (approx. 60 mins including questions) so that we have enough time to dive into the papers in sufficient detail to also cover and understand some of the relevant technical details. For the talks, we will have six meetings, each on a Monday between 10:15 and approx. 12:30. Attendance to those meetings is mandatory to pass the seminar. On Monday, 20.04., from 12:15 - 14:00 in room 101-01-016/18, there will be an introductory meeting to the seminar, where we will explain our plan for the seminar in more detail.

Note that you have to sign up to the seminar through HISinOne. The process of how to sign up for seminars and how the assignment of the seminar slots is organized is decribed here.

Topics and Schedule

Here is the list of seminar topics, along with the days on which the corresponding talks will take place.

Monday, 01.06.2026, 10:15 - 12:30: Presentations 1 + 2 (in room 101-01-016/18)

  1. A Model of Computation for MapReduce by Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. This paper provides one of the first rigorous theoretical frameworks for MapReduce. It defines the "MPC model" (Massively Parallel Computation), which captures the constraints of modern data processing: a limited number of machines, each with restricted memory, and a focus on minimizing the number of communication rounds.
    (presented by TBA, supervised by Marc Fuchs)
  2. Sorting, Searching, and Simulation in the MapReduce Framework by Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. This work explores how classic fundamental algorithms like sorting and searching can be adapted to the MapReduce model. It introduces the concept of "simulation," showing how algorithms designed for older parallel models (like PRAM) can be translated into efficient MapReduce programs.
    (presented by TBA, supervised by Justine Cauvi)

Monday, 08.06.2026, 10:15 - 12:30: Presentations 3 + 4 (in room 101-01-016/18)

  1. Filtering: A Method for Solving Graph Problems in MapReduce by Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Graph data is often too large to fit on one machine. This paper introduces the "Filtering" technique, where the graph is Sparsified (edges are removed) in each round while preserving key properties (like connectivity), eventually making the problem small enough to solve locally.
    (presented by TBA, supervised by Salwa Faour)
  2. Communication steps for parallel query processing by Paul Beame, Paraschos Koutris, and Dan Suciu. This paper analyzes the trade-off between the amount of data sent over the network and the number of rounds of computation. It focuses on relational join queries, establishing bounds on the communication cost required to process complex database queries in parallel.
    (presented by TBA, supervised by Justine Cauvi)

Monday, 15.06.2026, 10:15 - 12:30: Presentations 5 + 6 (in room 101-01-016/18)

  1. Parallel Graph Connectivity in Log Diameter Rounds by Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Finding connected components is a baseline graph problem. This paper presents an algorithm that solves connectivity in a very small number of rounds—specifically related to the logarithm of the graph's diameter—by using "neighborhood doubling" techniques.
    (presented by TBA, supervised by Fabian Kuhn)
  2. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover by Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. "Round compression" is the art of taking an algorithm that takes many rounds and squashing it into fewer rounds. This paper explores the theoretical limits of this technique, showing when it is possible to significantly speed up computation by increasing the work done per round.
    (presented by TBA, supervised by Salwa Faour)

Monday, 22.06.2026, 10:15 - 12:30: Presentations 7 + 8 (in room 101-01-016/18)

  1. Parallel algorithms for geometric graph problems by Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. This paper shifts the focus to computational geometry. It explains how to build geometric structures (like Voronoi diagrams or Convex Hulls) when the points are distributed across many machines, focusing on minimizing global communication.
    (presented by TBA, supervised by Marc Fuchs)
  2. Fully Scalable MPC Algorithms for Euclidean k-center by Artur Czumaj, Guichen Gao, Mohsen Ghaffari, and Shaofeng H.-C. Jiang. The $k$-center problem is a classic clustering task (e.g., where to place $k$ warehouses to minimize distance to customers). This paper provides an algorithm that is "fully scalable," meaning it remains efficient even as the memory per machine shrinks.
    (presented by TBA, supervised by Zahra Parsaeian)

Monday, 29.06.2026, 10:15 - 12:30: Presentations 9 + 10 (in room 101-01-016/18)

  1. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation by Mohsen Ghaffari and Jara Uitto. Finding a "Matching" (sets of edges with no shared vertices) is difficult in parallel. This paper provides an algorithm that finds a maximum matching in a number of rounds related to the square root of the maximum degree ($\Delta$).
    (presented by TBA, supervised by Fabian Kuhn)
  2. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds by Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. This is a "negative result" paper. It explores what we cannot do in the MPC model. It introduces conjectures (like the "Connectivity Conjecture") to show that certain problems likely cannot be solved faster than a certain number of rounds.
    (presented by TBA, supervised by Gustav Schmid)

Monday, 20.07.2026, 10:15 - 12:30: Presentations 11 + 12 (in room 101-01-016/18)

  1. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem by M´elanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. A 2-ruling set is a variation of the Maximal Independent Set. This paper provides an algorithm that is optimal in both time (rounds) and space (memory per machine), solving a core symmetry-breaking problem that is used as a building block for many other graph algorithms.
    (presented by TBA, supervised by Zahra Parsaeian)
  2. Massively Parallel Computation via Remote Memory Access by Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub ÅÄ…cki, Warren Schudy, and Vahab Mirrokni. Traditional MPC models assume the communication pattern is fixed. This paper introduces the "Adaptive MPC" model, where machines can decide who to talk to based on the data they see during the run. This model allows for even faster algorithms for problems like BFS and connectivity.
    (presented by TBA, supervised by Zahra Parsaeian)