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

图扩展是指将图划分为两个（或更多）大块，同时最小化它们之间“接口”的大小的问题。图分区或分隔符是马尔可夫链、几何嵌入等理论研究的中心对象，在许多情况下是一种自然的算法原语。精确计算是np困难的，所以我们感兴趣的是近似解。尽管做了很多工作，但与MAX-3SAT等更容易理解的问题相比，大多数扩展型问题的状态仍然是开放的。近年来，人们越来越清楚地认识到，类膨胀问题是解决许多近似问题的关键，比如独特游戏猜想（unique games conjecture，简称UGC，由Khot在PI的研究生时期提出）和小集膨胀猜想（Small-set expansion conjecture，由Raghavendra和Steuerer提出，Steurer 2010年论文的一部分由PI指导）。这个奖项的一个主要目标是应用新的谱（如特征值/特征向量）思想来研究图的展开。这些想法是在PI最近与Barak和Steurer合著的关于Unique Games问题的次指数算法的工作中引入的。这个奖项可能会导致变革性的结果，如唯一游戏猜想的解决，或基于全谱的图形划分的新算法（而不是仅使用第二个特征向量的算法，其局限性众所周知）。

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