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))
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)] |
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 times since Jan 26, 2019.
Prahladh Harsha |