Course projects
There will be a course project.
The purpose is to acquire a deeper understanding on a specific topic
of your own interest.
You are encouraged to pick any topic close to your own research interests.
Below are some suggested topics and references (will be updated from
time to time).
- sparsest cut - approximation algorithms for sparsest cut
- Arora, Rao, Vazirani. Expander Flows, Geometric Embeddings, and Graph Partitioning.
- graph separators - by spectral algorithms
- Spielman, Teng. Spectral Partitioning Works: Planar Graphs and Finite Element Meshes.
- Kelner. Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus Graphs.
- Biswal, Lee, Rao. Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows.
- Kelner, Lee, Price, Teng. Metric Uniformation and Spectral Bounds for Graphs.
- Colin de Verdiere number - a spectral characterization of planar graphs and more
- Godsil, Royle. Algebraic Graph Theory, Chapter 13.9-13.11.
- Spielman, L26, 2009.
- Lovasz, Schrijver. A Borsuk Theorem for Antipodal Links and a Spectral Characterization of Linklessly Embeddable Graphs.
- combinatorial optimization - using eigenvalues
- Mohar, Poljak. Eigenvalues in Combinatorial Optimization.
- Mohar. The Laplacian Spectrum of Graphs.
- extremal combinatorics - using eigenvalues
- Ellis, Friedgut, Pilpel. Intersecting Families of Permutations.
- Ellis, Filmus, Friedgut. Triangle Intersecting Families of Graphs.
- Filmus. Spectral Methods for Intersection Problems.
- unique games - and graph expansion
- Arora, Barak, Steurer. Subexponential Algorithms for Unique Games and Related Problems.
- Steurer, Raghavendra. Graph Expansion and the Unique Games Conjecture.
- semidefinite programming
- Barak, Steurer, Raghavendra. Rounding Semidefinite Programming Hierarchies via Global Correlation.
- Guruswami, Sinop. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives.
- small set expansion
- Steurer, Raghavendra, Tetali. Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters.
- Bansal, Feige, Krauthgamer, Makarychev, Nagarajan, Naor, Schwartz. Min-Max Graph Partitioning and Small Set Expansion.
- local graph partitioning
- Spielman, Teng. A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning.
- Anderson, Chung, Lang. Using Pagerank Vectors to Locally Partition a Graph.
- Anderson, Peres. Finding Sparse Cuts Locally Using Evolving Sets.
- expander graphs
- Hoory, Linial, Wigderson. Expander Graphs and Their Applications.
- random walk
- Levin, Peres, Wilmer. Markov Chains and Mixing Times.
- spectral clustering
- graph isomorphism
- pagerank, web graphs
- rubber bands, squaring square
- applications in machine learning
- spectral graph theory for directed graphs