Here is the course syllabus.

Readings will come from this draft of a book. You can find lecture notes from previous years here: (Fall 2018), (Fall 2015), (Fall 2012), (Fall 2009).

Not a lecture: Dan's favorite inequality

- Aug 28:
Introduction. Review of Graphs and Spectral Theory. Survey of highlights of the course.

Reading: Chapter 1 and Section 2.1. my notes

Files: 462Lect1.ipynb, 462Lect1.pdf, docec.txt, YALE.jld2. - Aug 30: The Laplacian Matrix and Spectral Graph Drawing. Courant-Fischer.

Reading: Section 2.2 and Chapter 3. my notes. - Sep 4: The Adjacency Matrix, interlacing, and Perron-Frobenius.

Reading: Chapter 4. my notes.**ps1 out.** - Sep 9: Eigenvalues and Graph Structure: cuts, partitions, and coloring.

Reading: Chapter on "Independent Sets and Coloring" (but not Section 4) and Chapter on "Graph Partitioning". (now numbered 18 and 19). my notes. - Sep 11: The Zoo of graphs. Bounding eigenvalues by test vectors.

Reading: Chapter 6. my notes. - Sep 16: Eigenvalue comparison theorems.

Reading: Chapter 5. my notes. The Jupyter Notebook. - Sep 18: Eigenvalues of random graphs.

Reading: Chapter 8. my notes. The Jupyter Notebook.

**ps1 due, ps2 out.** - Sep 23: Partitioning in Stochastic Block Models.

Reading: Chapter 22. my notes. The Jupyter Notebook. - Sep 25: Cheeger's inequality.

Reading: Chapter 21. my notes. - Sep 30: Random Walks on Graphs

Reading: Chapter 10. my notes. - Oct 2: Local graph clustering

**ps2 due, ps3 out.**my notes. - Oct 7: Spring and resistor networks

Reading: Chapter 11. my notes. - Oct 9: Elimination and Schur Complements. Effective Resistance.

Reading: Chapter 12. my notes. - Oct 14: Spring embeddings of planar graphs.

Reading: Chapter 15. my notes. - Oct 21: Computing Effective Resistance.

Reading: Chapter 14 and Section 12.3. my notes.

**ps3 due, ps4 out.** - Oct 23: Introduction to Expander Graphs

Reading: Chapter 27. my notes. - Oct 28: PSRGs via Random Walks on Expanders

Reading: Chapter 31, and maybe Section 4 of Chapter 7. my notes. - Oct 30: Introduction to Coding Theory

Reading: Chapter 28. my notes. - Nov 4: Expander Codes

Reading: Chapter 29. my notes.

**ps4 due, ps5 out.** - Nov 6: A simple construction of expander graphs

Reading: Chapter 30. my notes. - Nov 11: Sparsification of graphs by random sampling.

Reading: Chapter 32. my notes. - Nov 13: Linear-sized sparsifiers of graphs.

Reading: Chapter 33. my notes. - Nov 18: Iterative Solvers for Linear Equations.

Reading: Chapter 34. my notes.

**ps5 due, ps6 out.** - Nov 20: The Conjugate Gradient

Reading: Chapter 35. my notes. - Dec 2: Preconditioning by low-stretch spanning trees

Reading: Chapter 36. my notes. - Dec 4: Nearly-linear time Laplacian solvers.

Reading: Chapter 37. my notes.

**ps6 due.**