|
# |
Date |
Topic |
Lecture Slides |
Reading Material |
|
1 |
T January 20 |
Introduction, The Laplacian. |
Lecture 1 |
|
2 |
R January 22 |
Extremal Eigenvalues and Eigenvectors of the Laplacian and the Adjacency Matrix. |
Lecture 2 |
|
3 |
T January 27 |
The Other Eigenvalues and Eigenvectors of the Laplacian |
Lecture 3 |
|
4 |
R January 29 |
Graphic Inequalities and Lowerbounds on the Second Laplacian Eigenvalue |
Lecture 4 |
|
5 |
T February 3 |
Graph Cutting and Cheegers Inequality |
Lecture 5 |
See also those notes. |
|
6 |
R February 5 |
Cheeger's Inequality Contd., Spectral k-Clustering |
Lecture 6 |
See this paper |
|
7 |
T February 10 |
Random Walks and Eigenvalues |
Lecture 7 |
|
8 |
R February 12 |
PRGs and Random Walks on Expanders |
Lecture 8 |
|
9 |
T February 17 |
Guest Lecture: Maximal Inequalities on Product Graphs |
Lecture 9 |
See this paper, this paper, and this post |
|
10 |
R February 19 |
Expander Graphs and their Properties |
Lecture 10 |
|
11 |
T February 24 |
Cayley Graphs |
Lecture 11 |
See this paper, and this paper Ramanujan graph Construction |
|
12 |
R February 26 |
A Construction of Expanders |
Lecture 12 |
See also these notes for Zig-Zag Product. |
| 13 | T March 3 | Eigenvalues of Random Graphs (or, Random Graphs are Expanders) | Lecture 13 | See also this paper on Trace Method , this paper on eigenvalues of random graphs, and these notes on Wigner's Semi-Circle Law. |
| 14 | R March 5 | Spectral Algorithms for Unique Games | Lecture 14 | See also this paper |
| 15 | T March 10 | Ramanujan Graphs from 2-Lifts | Lecture 15 | See this paper |
| 16 | R March 12 | Ramanujan Graphs from 2-Lifts, contd. |
| 17 | T March 17 | Effective Resistance | Lecture 17 |
| 18 | R March 19 | Graph Sparsification by Effective Resistances | Lecture 18 | See also this paper |
| 19 |
T March 24 |
|
|
|
|
20 |
R March 26 |
|
|
|
| 21 | T March 31 | Twice-Ramanujan Sparsifiers | Final Presentations | See this paper |
| R April 2 | Preconditioning/ Sum-of-Squares Proofs | Final Presentations | Presentation 1, Presentation 2 |
|
23 | T April 7 | Codes on Graphs | Final Presentations | See these slides , this paper and this paper |
|
24 | R April 9 | Lossless Expanders | Final Presentations | See these slides, this paper , and this paper |
| 25 | T April 14 | Spectral Radius of Infinite Graphs | Final Presentations | See this paper |
| 26 | R April 16 | Matrix Bernstein Inequalities, Bounding Spectra of Random Graphs | Final Presentations | See this paper and this paper |
| 27 | T April 21 | Spectral Graph Theory in Robotics | Final Presentations | See these slides and this paper |
| 28 | R April 23 | Spectral Clustering, Clustering via Random Walks, Clustering via high order Cheeger. | Final Presentations | See this paper, this paper, and this paper |
| 29 | T April 28 | Spectral Graph Drawing | Final Presentations | See these slides and this paper |
| 30 | R April 30 | Quantum Random Walks, Consensus Learning | Final Presentations | See this paper |
| 31 | T May 5 | No class! | | |