Lecture notes
Notes will be updated the day before lecture. The latex template is created by John Watrous.
| Notes [pdf] |
Lecture 1 (Jan 6): Introduction
|
Lecture 2 (Jan 8): Cheeger's inequality
|
Lecture 3 (Jan 13): Cheeger's inequality
|
Lecture 4 (Jan 15): random walks
|
Lecture 5 (Jan 20): expander graphs: properties
|
Lecture 6 (Jan 22): expander graphs: constructions
|
Lecture 7 (Jan 27): expander graphs: applications
|
Lecture 8 (Jan 29): higher-order Cheeger inequality
|
Lecture 9 (Feb 3): improved Cheeger inequality
|
Lecture 10 (Feb 5): fastest mixing time, vertex expansion, and reweighted eigenvalues
|
Lecture 11 (Feb 10): reweighted eigenvalues for directed graphs and hypergraphs
|
Lecture 12 (Feb 12): small sparse cuts from random walks
|
Lecture 13 (Feb 24): expander decomposition
|
Lecture 14 (Feb 26): threshold rank decomposition
|
Lecture 15 (Mar 3): spectral sparsification, matrix concentration, and effective resistance
|
Lecture 16 (Mar 5): spectral sparsification via potential function
|