6.S899 Distributed Graph Algorithms (Fall 2014)
- Instructors: Mohsen Ghaffari and Stephan Holzer
- Units 2-0-4 Graduate H-level
- Time: Fridays 11:00-12:30
- Place: 4-145
- Note: If you are taking this course or listening to it, send an email to Mohsen to get added to the mailing list.
Course Description:
In this course, we study the basic techniques for designing, analyzing, and proving the limitations of distributed graph algorithms. The course will be technique-oriented. The topics can be divided into two parts:
-
The first part focuses on the issue of "locality" in graph problems. We study local symmetry-breaking problems such as graph coloring and maximal independent set, and then cover a number of locality-preserving network decomposition techniques.
-
In the second part of the course, we study "congestion", that is, the effect of communication limitations on distributed algorithms.
Here, the problems we study will typically be of “non-local” nature, that is, solving them (implicitly or explicitly) requires learning some faraway information.
We study some communication complexity lower bounds and a number of recent distributed algorithms for problems such as minimum spanning tree, shortest paths, and cut approximations.
We also cover a few generic algorithmic tools such as graph spanners and graph sparsification.
Grading:
Grading: Participation in class (20%), Problem sets (30%), Research project (50%).
Lecture Notes
- (09/05) Lecture 1: Graph Coloring in constant-degree graphs: The Cole-Vishkin technique, and Linial's lower bound. [Notes]
- (09/12) Lecture 2: Better Graph Colorings: Linial's algorithm, the Kuhn-Wattenhofer color reduction technique, and Kuhn's algorithm via defective-coloring. [Notes]
- (09/26) Lecture 3: Maximal Independent Set: Luby's algorithm, and the algorithm of Barenboim, Elkin, Pettie & Schneider via graph shattering. [Notes]
- (10/03) Lecture 4: Network Decompositions: The distributed algorithm of Awerbuch, Goldberg, Luby & Plotkin. [Notes]
- (10/10) Lecture 5: Minimum Spanning Trees: A streamlined version of the algorithm of Kutten & Peleg. [Notes]
- (10/17) Lecture 6: Communication-Based Lower Bounds: The Omega(D+sqrt{n}) round lower bound of Das Sarma et al. for Minimum Spanning Tree, Single Source Shortest Path, etc. [Notes]
- (10/31) Lecture 7: Single Source Shortest Path: (1+eps)-approximation via Nanongkai's Rounding Technique and Random Skeleton Construction. [Notes]
- (11/07) Lecture 8: Spanners: The Baswana-Sen Construction of Spanners. [Notes]
- (11/14) Lecture 9: Minimum-Cut: Connectivity Under Random Edge Sampling. [Notes]
- (11/21) Lecture 10: Minimum-Cut: Approximating Min-Cut. [Notes]
- (12/05) Lecture 11: All Pairs Shortest Path: Holzer & Wattenhofer's technique for pipelining BFSs, and extensions by Lenzen. [Notes]
Problem Sets
- Problem Set 1 due 10/03/2014: [PDF]
- Problem Set 2 due 10/31/2014: [PDF]