Graph expansion refers to the problem of partitioning a graph into two (or more) large pieces while minimizing the size of the "interface" between them. Graph partitions or separators are central objects of study in the theory of Markov chains, geometric embeddings, etc., and are a natural algorithmic primitive in numerous settings. Exact computation is NP-hard, so we are interested in approximate solutions. Despite much work, the status of most expansion-type problems is still open, in contrast to better-understood problems such as MAX-3SAT. In recent years it has become clearer that expansion-like problems hold the key to many of the remaining mysteries of approximation, such as the unique games conjecture or UGC (formulated by Khot when he was the PI's graduate student) and the Small-set expansion conjecture (formulated recently by Raghavendra and Steuerer, and part of Steurer's 2010 dissertation supervised by the PI).

A principal goal of this award is to apply new spectral (as in eigenvalues/eigenvectors) ideas to study graph expansion. These ideas were introduced in the PI's recent coauthored work with Barak and Steurer on subexponential algorithms for Unique Games problem.

This award may result in transformative outcomes such as resolution of the unique games conjecture, or new algorithms for graph partitioning based upon the full spectrum (as opposed to algorithms using just the second eigenvector whose limitations are well-known).

Project Start
Project End
Budget Start
2011-09-01
Budget End
2014-08-31
Support Year
Fiscal Year
2011
Total Cost
$458,000
Indirect Cost
Name
Princeton University
Department
Type
DUNS #
City
Princeton
State
NJ
Country
United States
Zip Code
08540