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)] |
| 9 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)] |
| 11 Apr | 18. Explicit Construction of Lossless Conductors Lossless conductors, explicit construction Ref:[Kop (Lecture 12)] |
| 16 Apr | 19. 2-lifts of graphs and Bipartite Ramanujan Graphs of
every degree Lifts of graphs, old and new eigenvalues of lifts of graphs, bipartite Ramanujan graphs of every degree Ref:[BL, HLW (Section 6), Spi (Lecture 25)] |
| 18 Apr | 20. Matching polynomial of a graph Godsil-Gutman analysis of matching polynomial Ref: [Spi (Lecture 26)] |
| 23 Apr | 21. Interlacing polynomials Interlacing family of polynomials, introduction to small-set expansion Ref: [Spi (Lecture 25)] |
| 25 Apr | 22. Hypercontractivity and small-set expansion small-set expansion of noisy hypercube, Bonami's lemma, (2,4)-hypercontractivity, hypercontractivity implies small-set expansion Ref: [O'D (Section 9.1, 9.5), BBHKSZ (Appendix B)] |
| 30 Apr | 23. Eigenspectrum of Johnson Scheme (part I) Johnson Scheme, up-down operators across slices of Boolean hypercube Ref: [DDFH (Section 2-3)] |
| 2 May | 24. Eigenspectrum of Johnson Scheme (part II) Eigenvectors and eigenvalues of Johnson graph and related graphs Ref: [DDFH (Section 2-3), Fil3] |
| 9 May | 25. Expansion in higher dimensions Expansion in hypergraphs, high dimensional expansions, link expanders, expansion definition via up-down and down-up random walks Ref: [SY, DDFH] |
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.
| [BBHKSZ] | Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou: Hypercontractivity, sum-of-squares proofs, and their applications. STOC 2012: 307-326 [DOI, arXiv] |
| [BL] | Yonatan Bilu, Nathan Linial:Lifts, Discrepancy and Nearly Optimal Spectral Gap*. Combinatorica 26(5): 495-519 (2006) [DOI] |
| [DDFH] | Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha: Boolean Function Analysis on High-Dimensional Expanders. APPROX-RANDOM 2018: 38:1-38:20 [DOI, arXiv] |
| [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. |
| [Fil3] | Yuval Filmus: An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube. Electr. J. Comb. 23(1): P1.23 (2016) [html] |
| [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] |
| [O'D] | Ryan O'Donnell, "Analysis of Boolean Functions", Cambridge University Press, 2014. [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. |
| [SY] | Tasuku Soma, Yuichi Yoshida: Spectral Sparsification of Hypergraphs. SODA 2019: 2570-2581 [DOI, arXiv] |
| [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 |
|