Date Topic Notes and Links
9/9 Intro, Min-Cuts, and Karger's Contraction Algorithm [Karger'93], [Karger,Stein'93], wikipedia, notes
9/11 Chernoff Bounds other Tools notes
9/16 Sparsification, Network Communication, Gossip [Karger'94], [Karp et al.'00], notes
9/18 Routing vs. Network Coding, Network Coded Gossip [Haeupler'11], [Ho et al.'11], notes
9/23 Network Coding in Dynamic Networks and Strong Routing Impossibility Results [Haeupler,Kuhn'12], [Dutta et al.'11]
9/25 Distributed Algorithms: Maximal Independent Set, Coloring, Maximal Matching [Luby'86], [Metivier et al.'10], notes
9/30 More on Distributed Coloring and MIS Algorithms notes
10/02 The Lovasz Local Lemma Probabilistic Method Book, notes
10/07 Routing in O(Congestion + Dilation), The Moser Tardos Algorithm and LLL Framework [Leigthon, Maggs, Rao'94], notes, [Moser, Tardos'10], notes
10/09 An Algorithm for the Lovasz Local Lemma [Moser, Tardos'10], notes
10/16 The Fully Assymmetric Lovasz Local Lemma, More Applications, and an Algorithm for Super-Polynomially Bad Events [Haeupler, Saha, Srinivasan'10], notes
10/23 (Approximate) Limited Independence [Naor, Naor'93], [Schmidt, Siegel, Srinivasan'95], notes
11/04 Fun with Balls and Bins notes
11/11 Coding for Interactive Communication I: Problem Definition, Achievable Error Rates, A simple Protocol for Large Alphabets [Schulman'96], [Ghaffari, Haeupler, Sudan'14], [Braverman, Rao'11]
11/13 Coding for Interactive Communication II: Tree Codes and Applications [Schulman'96], [Ghaffari, Haeupler, Sudan'14]
11/18 Coding for Interactive Communication III: List Decoding and Boosting Efficiency [Ghaffari, Haeupler'14], [Brakerski, Kalai'12]
11/20 Coding for Interactive Communication IV: A Simple and Communication Efficient Coding Scheme [Haeupler'14]
11/25 Research Project Presentations I
11/27 Thanksgiving
12/2 Research Project Presentations II
12/4 Research Project Presentations III