6.S898 Parallel Algorithms, MIT, Spring 2026


Instructor: Prof. Mohsen Ghaffari.
Teaching Assistants: Jaehyun Koo. Office hours Wednesdays 3:00-5:00 pm, in 32-G5 (open lounge).
Lecture Time & Place: Tuesdays and Thursdays 11:00-12:30 at 32-155.

Canvas: Parallel Algorithms 2026 on Canvas (for nonpublic material). If you want Canvas access but are not registered in the course, please send an email to the course TA describing your background and how you plan to participate in the course.
Piazza: Parallel Algorithms 2026 on Piazza (for discussions). Please make sure to enroll, especially if you are taking this course for credit.

Course Description: This is a graduate-level Theoretical Computer Science (TCS) course, focusing on the algorithmic foundations of parallel computing. It covers a wide range of tools and techniques for designing algorithms that can benefit from parallelism, thus running faster when we have access to multiple processors.

Prerequisites: Sufficient mathematical maturity to start a graduate-level algorithmic course, including comfort with the basics of algorithm design and analysis, basics of probability, and some prior exposure to randomized algorithms. For instance, having passed MIT's 6.1220/6.046 Design and Analysis of Algorithms would suffice. No background in distributed systems is required. If you're not sure whether you are ready for this course, please talk to Mohsen.

Grading: problem sets 50%, course project 30%, scribing and peer grading 20%. See the Canvas page for further instructions.

 

Tentative Syllabus:

The tentative plan for the course is to have 5 modules, sturctured as follows:

(Module 1, 6 lectures) Basics of parallel computation and classic algorithms: work-depth modeling and PRAM, as well as algorithms for list ranking, sorting and merging, tree computations, connected component computations, graph matching and maximal independent set.

(Module 2, 4 lectures) Complexity theory and derandomizations: P vs NC, RNC vs NC., perfect matching, randomized algorithms via isolation lemma, and derandomization. Efficient derandomizations via binary search in a k-wise independent space, and local rounding.

(Module 3, 4 lectures) Selected recent advances in parallel graph algorithms: New work-efficient and sublinear depth parallel algorithms for shortest path computations, strongly connected components, and depth-first search.

(Module 4, 4 lectures) Batch-dynamic parallel algorithms. Devising dynamic parallel algorithms that can adapt their solution quickly to changes in the input (without solving the problem from scratch) and level parallelism in this adaptation in a nearly ideal way. Example problems will include connected component identification, matching, density-based decomposition, graph orientation, and coloring.

(Module 5, 6 lectures) Massively Parallel Computation. Algorithm design for MapReduce-like settings of large-scale data processing in various memory regimes of the model, covering techniques like filtering, round compression, randomized sparsification for iterative computations, connections to locality in computation and the related impossibility results. Problems targeted in this subarea will include matching, connected components and minimum spanning tree, various clusterings, and submodular maximization.

The last week will be used for project presentations.


Lectures:

Deliverables and deadlines:

See the Canvas page for the released files. Accessibility