CS514 Advanced Algorithms II: Spectral Graph Algorithms

Time: Friday 12:10 pm - 3:10 pm

Place: Livingston, Lucy Stone Hall (LSH), B267

Instructor: Peng Zhang

Office hours: Wednesday 3 - 4 pm (Hill 444) or by appointment

Course description

You could think of this course as "advanced linear algebra with applications in graph theory." We will explore how eigenvalues and eigenvectors of graphs can help us understand graph structures and design efficient algorithms. We will cover basics in spectral graph theory, graph sparsification, solvers for Laplacian linear equations, interlacing polynomials for Ramanujan graphs and the Kadison-Singer problem.

Prerequisites

You will need knowledge of linear algebra, some familiarity with graphs, and comfort with mathematical proofs.

Reading materials

We will not have a textbook. But I highly recommend:

Spectral and Algebraic Graph Theory, by Daniel Spielman

Very good courses on spectral graph theory:

Spectral graph theory, by Daniel Spielman: http://www.cs.yale.edu/homes/spielman/462/462schedule.html

Spectral graph theory, by Lap Chi Lau: https://cs.uwaterloo.ca/~lapchi/cs860-2019/

Spectral graph theory, by Gary Miller: http://www.cs.cmu.edu/afs/cs/academic/class/15859n-s21/index.html

Assignments

Problem sets (60%): 3 problem sets

Project (25%): team project presentation (last week in class)

Scribe notes (15%)

Participation (5% bonus)

Schedule

Week 1: Introduction, basic spectral graph theory, bounding eigenvalues by the Courant-Fischer Theorem

Week 2: Isoperimetric number, conductance, Cheeger's inequality

Week 3: The zoo of graphs, their eigenvalues and eigenvectors

Week 4: Random walks on graphs

Week 5: Eigenvalues of random graphs

Week 6: Effective resistance, spectral sparsification by random sampling

Week 7: Better spectral sparsification by barrier functions

Week 8: Graph structured systems of linear equations, Gaussian elimination, Nested dissection

Week 9: Iterative methods, conjugate gradient

Week 10: preconditioning, fast Laplacian solvers

Week 11: Bipartite Ramanujan graphs and interlacing polynomials, Part I

Week 12: Bipartite Ramanujan graphs and interlacing polynomials, Part II

Week 13: Kadison-Singer and interlacing polynomials

Week 14: Project presentation