AF: Small: The Unique Games Conjecture and Related Problems in Hardness of Approximation

许多优化问题是np困难的，因此不可能有有效的算法。近似算法，通常基于几何技术，如线性和半定规划，是迄今为止最成功的对付np -硬度的方法。这个项目探索了它们的局限性，它的核心是一个证明独特游戏猜想的程序。在过去的二十年中，唯一对策猜想被广泛认为是近似硬度中的核心开放性问题。它的解决将解决大量优化问题的近似性，并证明几何技术的最优性。前面提到的关于独特游戏猜想的程序由两个独立的部分组成。(1)解决唯一对策猜想的布尔情况。研究者正在与几何泛函分析和概率方面的专家合作，以分析从np困难问题到布尔唯一游戏的简化。这种合作已经产生了一个里程碑式的成果，即分析了从np困难问题到布尔唯一对策的简化问题。(2)证明唯一对策猜想的布尔情形暗示了完整的唯一对策猜想。研究人员正在开发“强化”硬布尔唯一游戏的技术，这样它们就可以承认强平行重复，并暗示唯一游戏猜想。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Numerous optimization problems are NP-hard and thus unlikely to have efficient algorithms. Approximation algorithms, often based on geometric techniques like linear and semidefinite programming, are so far the most successful approach against NP-hardness. This project explores their limitations, and its heart is a program towards a proof of the Unique Games Conjecture. The Unique Games Conjecture is widely recognized as the central open problem in hardness of approximation in the past two decades. Its resolution would settle the approximability of a large number of optimization problems and prove the optimality of geometric techniques.The aforementioned program towards the Unique Games Conjecture consists of two independent components. (1) Resolve the Boolean case of the Unique Games Conjecture. The investigator is collaboraing with experts in geometric functional analysis and probability in order to analyze a reduction from an NP-hard problem to Boolean unique games. This collaboration has already led to a milestone, namely an analysis of a reduction from a problem in the same spirit as NP-hard problems to Boolean Unique Games. (2) Show that the Boolean case of the Unique Games Conjecture implies the full Unique Games Conjecture. The investigator is developing techniques for "fortifying" hard Boolean unique games so they admit strong parallel repetition and imply the Unique Games Conjecture.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.