Course projects
There is a course project that contributes 50% to the course grade. The goal of the project is to gain a deeper understanding on a specific topic or technique of your choice. You are encouraged to select a spectral graph theory-related topic close to your own research interests. The basic requirement is to read relevant papers and write a survey, of course you are encouraged to do original research if possible.
Below are some project ideas, mostly further references to topics relevant to the course.
- sparsest cut
- Expander flows, geometric embedding, and graph partitioning, by Arora, Rao, and Vazirani.
- maximum cut
- Max cut and the smallest eigenvalue, by Trevisan.
- spectral multi-partitioning
- Multi-way spectral partitioning and higher-order Cheeger inequalities, by Lee, Oveis Gharan and Trevisan.
- Many sparse cuts via higher eigenvalues, by Louis, Raghavendra, Tetali, and Vempala.
- improved Cheeger's inequalities
- Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap, by Kwok, Lau, Lee, Oveis Gharan and Trevisan.
- Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile, by Kwok, Lau, Lee.
- bounds on higher eigenvalues
- Spectral partitioning works: Planar graphs and finite element meshes, by Spielman and Teng.
- Metric uniformization and spectral bounds for graphs, by Kelner, Lee, Price, and Teng.
- planted random model
- Spectral partitioning of random graphs, by McSherry.
- A proof of the block model threshold conjecture, by Mossel, Neeman, and Sly.
- extremal combinatorics
- Intersecting families of permutations, by Ellis, Filmus, and Friedgut.
- Triangle intersecting families of graphs, by Ellis, Filmus, and Friedgut.
- Erdos-Ko-Rado theorems: algebraic approaches, by Godsil and Meagher.
- rapidly mixing Markov chains
- Markov chains and mixing time, by Levin, Peres, and Wilmer.
- local graph partitioning
- Finding sparse cuts locally using evolving sets, by Andersen and Peres.
- Approximating the expansion profile and almost optimal local graph clustering, by Oveis Gharan and Trevisan.
- spectral algorithms
- Spectral algorithms, by Kannan and Vempala.
- A tutorial on spectral clustering, by von Luxburg.
- unique games conjecture
- Subexponential algorithms for unique games and related problems, by Arora, Barak and Steurer.
- Graph expansion and the unique games conjecture, by Raghavendra and Steurer.
- small set expansion
- Hypercontractivity, sum-of-square proofs, and applications, by Barak, Brandao, Harrow, Kelner, Steurer, Zhou.
- Making the long code shorter, by Barak, Gopalan, Hastad, Meka, Raghavendra and Steurer.
- cut matching game
- Graph partitioning using single commodity flows, Khandekar, Rao, Vazirani.
- On partitioning graphs via single commodity flows, by Orecchia, Schulman, Vazirani, Vishnoi.
- expander graphs
- Expander graphs and their applications, by Hoory, Linial, and Wigderson.
- log space connectivity
- Pseudorandom walks on regular digraphs and the RL vs. L problem, by Reingold, Trevisan, and Vadhan.
- S-T Connectivity on Digraphs with a Known Stationary Distribution, by Chung, Reingold, and Vadhan.
- PCP theorem and expander graphs
- The PCP theorem by gap amplications, by Dinur.
- hypergraph expansion
- Spectral properties of hypergraph Laplacian and approximation algorithms, by Chan, Louis, Tang, Zhang.
- other generalizations of Cheeger inequalities
- Cheeger inequalities for submodular transformations, by Yoshida.
- A Schur complement Cheeger inequality, by Schild.
- electrical networks
- Electrical networks and random walks, by Doyle and Snell.
- Probability on trees and networks, by Lyons and Peres.
- graph sparsification
- Spectral sparsification of graphs: theory and algorithms, by Batson, Spielman, Srivastava, Teng.
- Constructing linear-sized spectral sparsification in almost-linear time, by Lee and Sun.
- hypergraph sparsification
- Near-linear size hypergraph cut sparsifiers, by Chen, Khanna, Nagda.
- Spectral hypergraph sparsifiers of nearly linear size, by Kapralov, Krauthgamer, Tardos, Yoshida.
- spectral rounding
- Near-optimal design of experiments via regret minimization, by Allen-Zhu, Li, Singh, Wang.
- A spectral approach to network design, by Lau, Zhou.
- A local search framework for experimental design, by Lau, Zhou.
- interlacing families
- Ramanujan graphs and the solution of the Kadison-Singer problem, by Marcus, Spielman, Srivastava.
- asymmetric traveling salesman problem
- Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP, by Anari and Oveis Gharan.
- The Kadison-Singer problem for strongly Rayleigh measures and applications to asymmetric TSP, by Anari and Oveis Gharan.
- high dimensional expanders
- High dimensional expanders, by Lubotzky.
- Course notes on high dimensional expanders, by Dinur.
- random walks on simplicial complexes
- Higher order random walks: Beyond spectral gap, by Kaufman and Oppenheim.
- Local spectral expansion approach to high dimensional expanders part I: descent of spectral gaps, by Oppenheim.
- Improved analysis of higher-order random walks and applications, by Alev, Lau.
- matroid expansion conjecture
- Log-concave polynomials I: entropy and a deterministic approximation algorithm for counting bases of a matroid, by Anari, Liu, Oveis Gharan, Vinzant.
- Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid, by Anari, Liu, Oveis Gharan, Vinzant.
- Modified log-Sobolev inequalities for strongly log-concave distributions, by Cygan, Guo, Mousa.
- spectral independence
- Spectral independence in high-dimensional expanders and applications to the hardcore model, by Anari, Liu, Oveis Gharan.
- locally testable codes
- Locally testable codes with constant rate, distance, and locality, by Dinur, Evra, Livne, Lubotzky, Mozes.
- Asymptotically good quantum and locally testable classical LDPC codes, by Panteleev, Kalachev.
- polytope diameter
- A spectral approach to polytope diameter, by Harayanan, Shah, and Srivastava.
- Colin de Verdiere number
- Graphs and geometry, by Lovasz.
- second eigenvalue multiplicity
- Support of closed walks and second eigenvalue multiplicity of graphs, by Lovasz.
- minimum cut
- Deterministic edge connectivity in near-linear time, by Kawarabayashi, Thorup.
- spectral spanners
- Composable core-sets for determinant maximization problems via spectral spanners.