Date 
Topic 
Notes and Links 
9/8 
Intro, MinCuts, and Karger's Contraction Algorithm 
[Karger'93], [Karger,Stein'93], wikipedia, notes 
9/10 
Chernoff Bounds other Tools, (Uniform) Sparsification 
[Karger'94], notes 
9/15 
Sparsification (by edge strengths) 
[Benczur,Karger'15]
, notes

9/17 
Network Gossip 
[Karp et al.'00], notes 
9/22 
Network Gossip II, Routing vs. Network Coding, Capacity Gap of Routing 
[Karp et al.'00], [Ho et al.'11]
, notes

9/27 
Random Linear Network Coding, MinCut Bound

[Ho et al.'11], notes

9/29 
Projection Analysis 
[Haeupler'11], notes 
10/01 
Network Coding in Dynamic Networks 
[Haeupler,Kuhn'12], [Dutta et al.'11], notes 
10/06 
Limited Independence, Constructions and Applications 
[Naor, Naor'93], notes

10/08 
Approximate Limited Independence and Chernoff Bounds 
[Alon, Goldreich, Hastad, Peralta'02], [Schmidt, Siegel, Srinivasan'93], notes 
10/13 
Johnson Lindenstrauss Lemma: Applications and Proof 
notes (by Anupam), [Indyk, Naor'07], subexponential RVs (Wainwright, Vershynin), notes 
10/15 
Compressed Sensing and the Johnson Lindenstrauss Lemma 
>notes (by Matousek), [Baraniuk et al.'08], more on compressed sensing, notes 
10/20 
The Lovasz Local Lemma 
AlonSpencer The Probabilistic Method (book), notes 

10/22 
Applying the LLL: Routing in O(Congestion + Dilation) 
[Leigthon, Maggs, Rao'94], notes 

10/27 
An Algorithm for the Lovasz Local Lemma 
[Moser, Tardos'10], notes 

10/29 
More Applications, and an Algorithm for SuperPolynomially Bad Events 
[Haeupler, Saha, Srinivasan'10], notes 

11/03 
The Fully Assymmetric Lovasz Local Lemma and Applications

[Haeupler, Saha, Srinivasan'10], [Moser, Tardos'10], notes 

11/05 
Parallel and Distributed and Deterministic Lovasz Local Lemma Algorihtms 
[Chandrasekaran, Goyal, Haeupler'10], [Moser, Tardos'10], notes 

11/10 
Models of Distributed Computing and Distributed Symmetrie Breaking 
[Luby'86], [Metivier et al.'10], notes 
11/12 
More on Distributed Symmetrie Breaking: Maximal Independent Sets, Coloring, and Maximal Matching 
[Luby'86], [Metivier et al.'10], notes 
11/19 
Coding for Interactive Communication 
[Haeupler'14]
 