Course projects
There will be a course project which contributes 50% to the course grade.
The purpose is to acquire a deeper understanding on a specific topic/technique of your own interest.
You are encouraged to pick any spectral graph theory related topic close to your own research interests.
The basic requirement is to read papers and write a survey, of course you are most welcome to do original research.
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.
- electrical networks
- Electrical networks and random walks, by Doyle and Snell.
- Probability on trees and networks, by Lyons and Peres.
- Laplacian solvers and their applications
- 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.