COL863: Special Topics in Theoretical Computer Science
Topic: Spectral Graph Theory

II semester: 2017-18

Amitabha Bagchi



Class Timings: Mon Thu 3:30PM-5PM.
Room: Bharti 106.

Topics

Spectral theorem for symmetric matrices, the Laplacian, Rayleigh quotient, Eigenvalues of the Laplacian, Spectral partitioning, Cheeger's inequality, Random walks on graphs, Effective resistance, Pseudo-random generators from random walks, Sparsification.

Note: The list of topics is tentative. We will amend it as we go along based on progress and class interest.

Background required: Linear Algebra, Graph Theory, Probability.

Texts

Note: We will basically follow the presentation in [Spielman2015].

Other links

Refresher texts

Problem sets

Evaluation

Refresher problem set 10%. Best 3 out of 4 minors 30% each.
Amitabha Bagchi