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 (May 12): Introduction overview (chapter 0) and course information linear algebra (appendix A) and graph spectrum (chapter 1)

Lecture 2 (May 14): Cheeger's inequality chapter 2.1-2.3

Lecture 3 (May 19): Random Walks chapter 2.4, 3.1-3.2

Lecture 4 (May 21): Random walks and expander graphs chapter 3.3-3.4, 4.1-4.2

Lecture 5 (May 26): Expander graphs: properties chapter 4.3-4.4

Lecture 6 (May 28): Expander graphs: constructions chapter 4.5, 5.1-5.3

Lecture 7 (June 2): Expander graphs: applications chapter 6

Lecture 8 (June 4): Spectral sparsification chapter 14.1-14.4

Lecture 9 (June 9): Matrix concentration chapter 23.1-23.4

Lecture 10 (June 11): Matrix Khintchine and CSP refutation chapter 23.5-23.6, 24.1

Lecture 11 (June 16): CSP refutation chapter 24.2-24.4

Lecture 12 (June 18): Kikuchi matrices chapter 25.1, 25.4

Lecture 13 (June 23): Locally decodable codes chapter 25.2

Lecture 14 (June 25): Hypergraph Moore bound and cut-matching game chapter 25.3, 17.1, 17.3

Lecture 15 (June 30): Cut-matching game chapter 17.2

Lecture 16 (July 7): Matrix multiplicative weight update chapter 18

Lecture 17 (July 9): Sherman's algorithm chapter 19

Lecture 18 (July 14): Small sparse cuts chapter 11

Lecture 19 (July 16): Subexponential algorithms for Unique Games chapter 13

Lecture 20 (July 21): Local-to-global rounding on expander graphs chapter 20

Lecture 21 (July 23): Local-to-global rounding on low threshold rank graphs chapter 21

Lecture 22 (July 28): Local-to-global rounding on low general graphs? chapter 22

Lecture 23 (July 30): High-dimensional expanders chapter 26

CS, Waterloo.