Date Topic Notes and Links
9/8 Intro, Min-Cuts, 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, Min-Cut 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], sub-exponential 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 Alon-Spencer 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 Super-Polynomially 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]