6.S899 Distributed Graph Algorithms (Fall 2014)
 Instructors: Mohsen Ghaffari and Stephan Holzer
 Units 204 Graduate Hlevel
 Time: Fridays 11:0012:30
 Place: 4145
 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 techniqueoriented. The topics can be divided into two parts:

The first part focuses on the issue of "locality" in graph problems. We study local symmetrybreaking problems such as graph coloring and maximal independent set, and then cover a number of localitypreserving 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 “nonlocal” 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 constantdegree graphs: The ColeVishkin technique, and Linial's lower bound. [Notes]
 (09/12) Lecture 2: Better Graph Colorings: Linial's algorithm, the KuhnWattenhofer color reduction technique, and Kuhn's algorithm via defectivecoloring. [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: CommunicationBased 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 BaswanaSen Construction of Spanners. [Notes]
 (11/14) Lecture 9: MinimumCut: Connectivity Under Random Edge Sampling. [Notes]
 (11/21) Lecture 10: MinimumCut: Approximating MinCut. [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]