Site menu:

• Information
• Notes
• Project

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.

CS, Waterloo.