| Week |
Topic and Reading | Handout |
| Jan 12 |
Administrivia Review of probability and graph algorithms Random walks in graphs Cover time in regular graphs Primary references:
Laszlo Lovasz, Random Walks on Graphs, 1994; Sections 0, 1, 2, and 3
Secondary references:
Michael Mitzenmacher and Eli Upfal, Probability and Computing, 2005, Chapter 7
| Lecture Notes |
| Jan 15 |
Random walks in graphs Cover time, mixing time, and spectral gap Primary references:
Laszlo Lovasz, Random Walks on Graphs, 1994; Section 3 and first half of 5.
| Lecture Notes |
| Jan 19 |
Random walks in graphs Random walks and electrical networks Rumor spreading and gossiping Network diffusion processes Analysis of push-based broadcast Primary references:
Laszlo Lovasz, Random Walks on Graphs, 1994; Section 4
Secondary references:Feige, Peleg, Raghavan, and Upfal, Randomized broadcast in networks, RSA 2006 Peter Doyle and J. Laurie Snell, Random walks and electrical networks, 1984, 2000, Chapter 1
| Lecture Notes |
| Jan 22 |
Rumor spreading and gossiping Analysis of the push-pull protocol in general graphs Primary reference: G. Giakkoupis, Tight Bounds for Rumor Spreading for Graphs of a Given Conductance, STACS 2011
Secondary reference:F. Chierichetti, S. Lattanzi, A. Panconesi, Rumor Spreading in Social Networks, ICALP 2009
F. Chierichetti, S. Lattanzi, A. Panconesi, Almost Tight Bounds for Rumor Spreading with Conductance, STOC 2010 G. Giakkoupis, Tight Bounds for Rumor Spreading with Vertex Expansion, SODA 2014
| Problem Set 1 Lecture Notes |
| Jan 26 |
Cris Moore Colloquium Talk: What can physics tell us about inference? | |
| Jan 29 |
Rumor spreading and gossiping Analysis of the push-pull protocol in general graphs Primary reference: G. Giakkoupis, Tight Bounds for Rumor Spreading for Graphs of a Given Conductance, STACS 2011
| Lecture Notes |
| Feb 2 |
Rumor spreading and gossiping Optimal gossiping using network coding Bernhard Haeupler, Analyzing Network Coding Gossip Made Easy, STOC 2010 | Lecture Notes |
| Feb 5 |
Epidemics The SIR model: Idealized analysis using branching processes Rick Durrett, Random Graph Dynamics, Cambridge University Press D. Easley and J. Kleinberg, Networks, Crowds, and Markets, Cambridge U. Press, 2010 | Lecture Notes |
| Feb 9 |
Epidemics The SIR model: Idealized analysis using branching processes Talk on Reed-Solomon codes by Mary Wootters | |
| Feb 12 |
Epidemics Ganesh, Massoulie, and Towsley, The effect of network topology on the spread of epidemics, Infocom 2006 Upper bound on epidemic die-out in terms of spectral radius | Lecture Notes |
| Feb 16 |
Epidemics Ganesh, Massoulie, and Towsley, The effect of network topology on the spread of epidemics, Infocom 2006 Lower bound on epidemic die-out time, when expansion is high Small worlds Decentralized search Power law graphs D. Easley and J. Kleinberg, Networks, Crowds, and Markets, Cambridge U. Press, 2010 | Lecture Notes |
| Feb 19 |
Graph Sparsification Random sampling algorithm of Karger Spanners and cut sparsifiers Benczur and Karger, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, STOC 2002 Nick Harvey's notes | Lecture Notes |
| Feb 23 |
Graph Sparsification Cut sparsifier using connectivity Fung, Hariharan, Harvey, and Panigrahi, A general framework for graph sparsification, STOC 2011 Debmalya Panigrahi's notes | Lecture Notes (same as above) |
| Feb 26 |
Graph Sparsification Spectral sparsifiers Spielman and Srivastava, Graph Sparsitication by Effective Resistances, SICOMP 2011 Nick Harvey's notes | Lecture Notes |
| Mar 1 |
Graph Sparsification Spectral sparsifiers, contd | Lecture Notes |
| Mar 4 |
Streaming Models, sampling methods Frequent elements (Misra-Gries) Amit Chakrabarti's notes | Lecture Notes |
| Mar 8 |
Spring Break | |
| Mar 11 |
Spring Break | |
| Mar 15 |
Streaming Distinct elements (Alon-Matias-Szegedy) Amit Chakrabarti's notes | Lecture Notes |
| Mar 18 |
Streaming Frequency moments Alon, Matias, and Szegedy, The space complexity of approximating the frequency moments, JCSS 1999 | |
| Mar 22 |
Streaming Graph streaming: connectivity, spanning trees Andrew McGregor, Graph stream algorithms: A survey, ACM SIGMOD Record, 2014 | |
| Mar 25 |
Embedding Distance-based embedding into trees Fakcharoenphal, Rao, and Talwar, A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics, JCSS 2004 Elkin, Emek, Spielman, and Teng, Lower-Stretch Spanning Trees, SICOMP 2008 Avner Magen's notes Chandra Chekuri's notes | |
| Mar 29 |
Embedding Cut-based embedding into trees Räcke, Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC 2008 | |
| Apr 1 |
Rounding of Linear Programs Edge-disjoint paths; multicommodity flow Randomized rounding Williamson and Shmoys, The Design of Approximation Algorithms, Cambridge U. Press | |
| Apr 5 |
Rounding of Semi-Definite Programs Goemans and Williamson on Max-Cut Williamson and Shmoys, The Design of Approximation Algorithms, Cambridge U. Press | |
| Apr 8 |
The Primal-Dual Paradigm Steiner network design Williamson and Shmoys, The Design of Approximation Algorithms, Cambridge U. Press | |
| Apr 12 |
The Primal-Dual Paradigm | |
| Apr 15 |
The Multiplicative Weight Update Method Arora, Hazan, and Kale, The Multiplicative Weights Update Method: A Meta-Algorithm and its Applications, Theory of Computing 2012 | |
| Apr 19 |
No class | |
| Apr 22 |
Project Presentations | |
| Apr 26 |
Project Presentations |