**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 closely related to the course. The requirement is 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.
**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.
**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.
**Gurvits permanent inequalities**- Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications, by Gurvits.
- A generalization of permanent inequalities and applications in counting and optimization, by Anari and Oveis Gharan.
**local lemma and polynomials**- The repulsive lattice gas, the independent-set polynomial, and the Lovasz local lemma, by Scott, Sokal.
**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.
**completely 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.
**spectral independence**- Spectral independence in high-dimensional expanders and applications to the hardcore model, by Anari, Liu, Oveis Gharan.
**fractionally log-concave polynomials**- Fractionally log-concave and sector-stable polynomials: counting planar matchings and more, by Alimohammadi, Anari, Shiragur, Vuong.
**entropic independence**- Entropic independence I: Modified log-Sobolev inequalities for fractionally log-concave distributions and high-temperature Ising models, by Anari, Jain, Koehler, Pham, Vuong.
- Entropic independence II: Optimal sampling and concentration via restricted modified log-Sobolev inequalities, by Anari, Jain, Koehler, Pham, Vuong.
**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.
**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.