Expander Graphs and their applications - Fall 2020 course

Lecturer: Irit Dinur
Time: Monday+Tuesday 9:30 - 11:00
Start date: Monday, November 2, 2020

[Zoom link]

This is a basic introductory course to expander graphs. Expanders are fundamental objects with many applications in computer science and beyond. We will learn about basic properties of expander graphs and some of the most fascinating applications such as towards constructing error correcting codes, derandomization, networks, approximate counting, and more.

Exercises: [ex1 (due Nov 16)] Take the survey about the exercise

Lectures by weeks:
  1. [Video L01] [ppt L01], [Video L02] [notes L02]
    Introduction and three applications of expander graphs. Based on chapter 1 in HLW.

  2. [Video L03] [notes L03] [Video L04] [notes L04]
    Combinatorial expansion, and spectral / algebraic expansion. The expander mixing lemma (EML). Partly based on chapter 2 in HLW.

  3. [Worksheet L05] ("inverse classroom" - worked on problems in groups, here are solutions by "Group 1")

  4. [Video L06] [notes L06] Spectral theorem, the Laplacian of a graph, Cheeger's inequality connecting edge expansion and spectral gap.
    [Video L07] [notes L07] Random walks
Resources:
  1. Survey on "EXPANDER GRAPHS AND THEIR APPLICATIONS" by Hoory Linial and Wigderson [HLW]

  2. Lecture notes from a course by Linial and Wigderson with the same title

  3. Lecture notes on expansion and spectral graph theory by Luca Trevisan

  4. Book on spectral and algebraic graph theory by Dan Spielman