Date Notes Last Updated Topics Additional References
Weeks 1&2 pdf 2/9/12 Graphs, Trees, Random Walks, Random Spanning Trees Random Walks Survey (Lovasz)
Random Walks and Electric Networks (Doyle and Snell)
Random Walks on Graphs (Aldous and Fill)
Generating Random Spanning Trees (Broder)
Week 3 pdf 2/2/12 Network Flow, Max-flow/Min-cut Algorithms and Applications CS 261 Max-flow Notes (Lec. 9-11) (Trevisan)
Kleinberg and Tardos Ch. 7
Week 4 pdf 2/9/12 Global Min-Cut and Network Reliability A New Approach to the Minimum Cut Problem (Karger and Stein)
Week 5 pdf 2/9/12 Matching and Matrix Inversion Matching is as Easy as Matrix Inversion (Mulmuley, Vazirani, and Vazirani)
Week 6 See Papers 2/14/12 Perfect Matching in Regular Bipartite Graphs Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs (Goel, Kapralov, Khanna) - Edge Sparsification
Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs (Goel, Kapralov, Khanna) - Augmenting Paths
Week 7 pdf 2/25/12 Graph Sparsification and the Probabilistic Method The Probabilistic Method (Alon and Spencer)
Week 8 pdf 3/3/12 Sparsification via Effective Resistances Graph Sparsification via Effective Resistances
Week 9 pdf 3/10/12 Reduction, Problem Classes, and Approximation Algorithms The NP Compendium
Kleinberg and Tardos Ch. 8
Week 10 See Paper 3/15/12 TSP and Topics of Current Research An O(log n/log log n)-approximation Algorithm for ATSP


Please send any error reports or requests for more exposition to Ed Schmerling (schmrlng [AT] stanford [DOT] edu).