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
- [Spielman2015] Daniel A. Spielman. Lecture notes of Spectral Graph Theory, Fall 2015, Yale University. Available here.
- [Chau2015] Lap Chi Chau. Lecture notes of CS798, Spectral Graph Theory, 2015, University of Waterloo. Available here.
Note: We will basically follow the presentation in [Spielman2015].
Other links
- Keith Conrad. Linear independence of characters, University of Connecticut, undated. Download here.
- For a general statement of the Perron-Frobenius theorem with proof, see Chapter 9 of the book Dynamical Systems by Shlomo Sternberg.
The entire book can be downloaded at this link.
- [Trevisan2014] Luca Trevisan. Lecture notes on Expansion, Sparsest Cut, and Spectral Graph Theory, 2014. Available here.
Refresher texts
Problem sets
- Minor 4. Read description here. Due on moodle by 11:55PM, 1 May 2018.
- Minor 3. Read description here. Due on moodle by 11:55PM, 11 April 2018.
- Minor 2. Download here. Latex template available on moodle. Due on moodle by 11:55AM, 12 March 2018.
- Minor 1. Download here. Latex template available on moodle. Due on moodle by 11:55AM, 2 February 2018.
- Linear Algebra refresher problem set. Download here. Due at the beginning of class, 3:30PM, 11 January 2018.
Evaluation
Refresher problem set 10%. Best 3 out of 4 minors 30% each.
Amitabha
Bagchi