Site menu:

• Information
• Notes
• Project

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 overview (chapter 1) and course information linear algebra (appendix A.1) and graph spectrum (chapter 2)

Lecture 2 (Jan 8): Cheeger's inequality Laplacian matrix (chapter 2) and started chapter 3

Lecture 3 (Jan 13): Cheeger's inequality chapter 3

Lecture 4 (Jan 15): random walks chapter 4

Lecture 5 (Jan 20): expander graphs: properties chapter 5.1-5.3

Lecture 6 (Jan 22): expander graphs: constructions chapter 5.4, chapter 6

Lecture 7 (Jan 27): expander graphs: applications chapter 7

Lecture 8 (Jan 29): higher-order Cheeger inequality chapter 8

Lecture 9 (Feb 3): improved Cheeger inequality chapter 9

Lecture 10 (Feb 5): fastest mixing time, vertex expansion, and reweighted eigenvalues chapter 10

Lecture 11 (Feb 10): reweighted eigenvalues for directed graphs and hypergraphs chapter 11

Lecture 12 (Feb 12): small sparse cuts from random walks chapter 12

Lecture 13 (Feb 24): expander decomposition chapter 13

Lecture 14 (Feb 26): threshold rank decomposition chapter 14

Lecture 15 (Mar 3): spectral sparsification, matrix concentration, and effective resistance chapter 15.1-15.3

Lecture 16 (Mar 5): spectral sparsification, matrix concentration, and effective resistance chapter 15.4-15.5, appendix C

Lecture 17 (Mar 10): spectral sparsification via potential function chapter 16

Lecture 18 (Mar 12): spectral sparsification and algorithmic discrepancy theory chapter 17

Lecture 19 (Mar 17): high-dimensional expanders chapter 18.1-18.3

Lecture 20 (Mar 19): high order random walks chapter 18.4, 19.1-19.2

Lecture 21 (Mar 24): spectral independence chapter 19.3, 20.1-20.2

Lecture 22 (Mar 26): cut-matching games chapter 21

Lecture 23 (Mar 31): matrix multiplicative weight update chapter 22

Lecture 24 (Apr 2): finishing up chapter 20.3-20.5, 16.6

CS, Waterloo.