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)]

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, 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


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.

[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 ]

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!