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)]
  2. Problem Set 2 [pdf (out: 12 Mar, due: 28 Mar)]


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, Fil1 (Chapter 3)]
20 Feb 7. Triangle-Intersecting Families of Graphs (Guest Lecturer: Yuval Filmus)
Ref: [Fil1 (Chapter 4)]
21 Feb 8. Planted Clique (Guest Lecturer: Yuval Filmus)
Finding cliques in planted clique, Feige-Krauthgamer algorithm using Lovasz Theta function
Ref: [Fil2 (Section 10), FK]
26 Feb 9. Delsarte's Linear Programming Bound
Introduction to codes, Rate-vs-distance question, elementary bounds, Delsarte's LP bound, Proof of LP bound via MacWilliams Identities
Ref: [notes, Gur (Notes 4, 5a, 5b), Sch]
28 Feb 10. Fourier proof of first MRRW bound
Navon-Samrodnitsky and Friedman-Tillich proof of first MRRW bound for codes
Ref: [Gur (Notes 5b), NS, FT]
5 Mar Class cancelled
7 Mar 11. Random Walks
Random walks on undirected graphs, transition matrix, examples: path, dumbbell graph
Ref: [Spi (Lecture 10)]
12 Mar 12. Expander Graphs
Spectral Expanders, exapnders as approximations of complete graphs, expander mixing lemma, vertex expansion
Ref: [Spi (Lecture 17), Vad (Section 4.1.2)]
14 Mar 13. Infinite d-tree and bounds on 2nd eigenvalue
Ramanujan graphs, infinite d-tree and bounds on its spectrum, Nilli's proof of Alon-Boppana bound
Ref: [ Luca Trevisan's blog "In Theory" (blogpost 1, blogpost 2)]
26 Mar 14. Undirected Connectivity and Nisan's PRG (Guest Lecturer: Jaikumar Radhakrishnan)
Randomized algorithm for undirected connectivity, Nisan's pseudo-random generator construction
Ref: [DH (Lectures 3-4), Nis]
28 Mar 15. Zig-Zag Product(Guest Lecturer: Jaikumar Radhakrishnan)
Graph operations: squaring, zig-zag product; undirected connectivity in logspace using zig-zag product, construction of expanders using zig-zag product.
Ref: [Vad (Sections 4.3-4.4)]
2 Apr 16. Zig-Zag Product Analysis
Spectral Analysis of zig-zag product. Unbalanced lossless expanders, Unique neighbour expansion, expander codes
Ref: [Vad (Section 4.3.2), Gur (Notes 8)]
10 Apr 17. Lossless Expanders and Applications to Coding
Unbalanced lossless expanders, application to coding: linear time decoding of expander codes, conductors, conductors from spectral expanders
Ref:[Gur (Notes 8), Kop (Lecture 12)]
12 Apr 18. Explicit Construction of Lossless Conductors
Lossless conductors, explicit construction
Ref:[Kop (Lecture 12)]

Tentative schedule for Future Lectures


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.

[DH] A course on Expander Graphs (offered by Cynthia Dwork and Prahladh Harsha) at Stanford: CS369E: Expanders in Computer Science, Spring 2005.
[Fil1] Yuval Filmus, Spectral methods in extremal combinatorics, PhD thesis, University of Toronto, 2013.
[Fil2] A course on Random Graphs (offered by Yuval Filmus) at Technion: Random graphs, Winter 2017-18.
[FK] Uriel Feige, Robert Krauthgamer: Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms 16(2): 195-208 (2000) [DOI]
[FT] Joel Friedman, Jean-Pierre Tillich: Generalized Alon--Boppana Theorems and Error-Correcting Codes. SIAM J. Discrete Math. 19(3): 700-718 (2005) [DOI]
[Gur] Venkatesan Guruswami, "15-859V: Introduction to Coding Theory", CMU, Spring 2010.
[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]
[Kop] A course on pseudorandomness (offered by Swastik Kopparty) at Rutgers: 198:596 Topics in Complexity Theory and Pseudorandomness, Spring 2013.
[NS] Michael Navon, Alex Samorodnitsky: Linear Programming Bounds for Codes via a Covering Argument. Discrete & Computational Geometry 41(2): 199-207 (2009) [DOI]
[Nis] Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica 12(4): 449-461 (1992) [DOI]
[Sch] Alexander Schrijver: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Information Theory 25(4): 425-429 (1979) [DOI]
[Spi] A course on Spectral Methods offered (by Dan Spielman) at Yale University: CPSC 662 / AMTH 561 : Spectral Graph Theory, Fall 2018.
[Vad] Salil Vadhan. Pseudorandomness (Monograph). Foundations and Trends in Theoretical Computer Science: Vol. 7: No. 1–3, pp 1-336, now publishers, 2012. [ html ]


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!