Site menu:

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