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

AF：小：扩展、独特的游戏和高效的算法

• 批准号: 1117309
• 负责人: Sanjeev Arora
• 金额: $ 45万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117309&HistoricalAwards=false
• 关键词: AF; Small; Expansion; 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).

图扩展是指将图划分为两个（或更多）大块，同时最小化它们之间的“接口”大小的问题。图的划分或分离器是马尔可夫链、几何嵌入等理论的中心研究对象，并且在许多设置中是自然的算法基元。精确计算是NP难的，所以我们对近似解感兴趣。尽管做了很多工作，但大多数扩展型问题的状态仍然是开放的，与MAX-3SAT等更好理解的问题相反。近年来，人们越来越清楚地认识到，类扩张问题是解决许多剩余的近似之谜的关键，例如独特博弈猜想或UGC（由Khot在他还是PI的研究生时提出）和小集合扩张猜想（最近由Raghavendra和Steuerer提出，Steuerer 2010年由PI监督的论文的一部分）。该奖项的主要目标是应用新的谱（如特征值/特征向量）思想来研究图扩展。这些想法在PI最近与Barak和Steurer共同撰写的关于唯一博弈问题的次指数算法的工作中被引入。该奖项可能会产生变革性的成果，例如解决唯一博弈猜想，或基于全谱的图分区新算法（而不是仅使用第二特征向量的算法，其局限性众所周知）。