AF: Small: Expansion, Unique Games, and Efficient Algorithms

点击翻译按钮获取中文摘要

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).