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

Prahladh Harsha
Valid HTML 4.01! Valid CSS!