Spectral Methods in Computer Science and Combinatorics - Winter/Summer Semester (2018-19)


Time: Tue Thu 11:30-13:00
Location: A201
Instructors :
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2017-18/spectral/

Course Calendar (Click here to subcribe to the calendar (ical format))


spectral: (adjective) /ˈspɛktr(ə)l/ of or like a ghost


Problem Sets

  1. Problem Set 1 [pdf (out: 7 Feb, due: 21 Feb)]

Lectures

29 Jan 1. Introduction
Administrivia; Course Contents; Examples of simple graphs, Matrices: Adjacency, Transition, Laplacian; Spectral Theorem; Rayleigh Coefficient; Hoffman Bound and application to Erdos-Ko-Rado
Ref:[HS (Spectral Methods module), Spi (Lecture 1 (Sec 1.4-1.6), Lecture 6 (Sec 6.1-6.3)), Jupyter Notebook (source code]
31 Jan 2. Basic Spectral Theory and some applications
Courant Fischer Theorem; Eigenvalues of Adjacency Matrix; Wilf-bound for chromatic number; Laplacian examples: complete graph, line graph, cycle
Ref: [HS (Spectral Methods module), Spi (Lecture 2 (Sec 2.1-2.2), Lecture 3 (Sec 3.1-3.4, 3.7))]
5 Feb 3. Spectrum of some fundamental graphs
Spectrum of cycles, paths, product-graphs, grid-graphs, Boolean hypercube, Cayley graphs; Edge-expansion, conductance of graph
Ref: [HS (Spectral Methods module), Spi (Lecture 3 (Sec 3.5, 3.7, 3.8))]
7 Feb 4. Cheeger Inequalities (Part I)
Generalized Laplacian, eigenspectrum of random walk matrix, Cheeger Inequalities, Proof of easy direction
Ref: [HS (Spectral Methods module), Spi (Lecture 11)]
12 Feb 5. Cheeger Inequalities (part II)
Proof of hard direction, Fieldler's spectral partitioning algorithm, Trevisan's analysis, tight examples.
Ref: [notes, HS (Spectral Methods module), Spi (Lecture 11), Luca Trevisan's blog "In Theory" (blogpost 1, blogpost 2) ]
14 Feb 6. Lovasz Theta Function and Applications (Guest Lecturer: Yuval Filmus)
Lovasz Theta function, Hoffman and Schrijver bound, Traffic light puzzle, Applications
Ref: [notes, Fil (Chapter 3)]
20 Feb 7. Triangle-Intersecting Families of Graphs (Guest Lecturer: Yuval Filmus)
Ref: [Fil (Chapter 4)]

Tentative schedule for Future Lectures


References

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

  1. [Fil] Yuval Filmus, Spectral methods in extremal combinatorics, PhD thesis, University of Toronto, 2013.
  2. [HS] A module on Spectral Methods in the course on Toolkit for Theoretical Computer Science (offered by Prahladh Harsha and Piyush Srivastava at TIFR, Monsoon 2018: [pdf]
  3. [Spi] A course on Spectral Methods offered (by Dan Spielman) at Yale University: CPSC 662 / AMTH 561 : Spectral Graph Theory, Fall 2018.

Requirements

Students taking the course for credit will be expected to:

This page has been accessed at least several times since Jan 26, 2019.


Prahladh Harsha
Valid HTML 4.01! Valid CSS!