## Spectral Methods in Computer Science and Combinatorics - Winter/Summer Semester (2018-19)

Time: Tue Thu 11:30-13:00
Location: A201
Instructors :

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

#### 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.

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

#### Requirements

Students taking the course for credit will be expected to:

• Attend lectures
• Do problem sets (approx 1 pset every 2.5 weeks)
• Give a presentation

This page has been accessed at least times since Jan 26, 2019.