Course projects
This is a research-oriented graduate course.
The main course work is the course project.
Students are expected to do active research on a topic in spectral graph theory.
The requirements include two presentations and a written report.
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.
- expander graphs
- Expander graphs and their applications, by Hoory, Linial, and Wigderson.
- 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.
- high dimensional expanders
- High dimensional expanders, by Lubotzky.
- Course notes on high dimensional expanders, by Dinur.
- random walks on simplicial complexes
- High dimensional expanders imply agreement expanders, by Dinur and Kaufman.
- 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.
- Boolean function analysis on high-dimensional expanders, by Dinur, Dikstein, Filmus, Harsha.
- 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.
- 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.
- real stable polynomials
- Zeros of polynomials and their applications to theory: a primer, by Vishnoi.
- Multivariate stable polynomials: theory and applications, by Wagner.
- 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.
- log-concave polynomials
- Log-concave polynomials III: Mason's ultra-log-concavity conjecture for independent sets of matroids, by Anari, Liu, Oveis Gharan, Vinzant.
- Lorentzian polynomials, by Branden and Huh.