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

许多优化问题都是NP难的，因此不太可能有有效的算法。近似算法通常基于几何技术，如线性规划和半定规划，是迄今为止最成功的对抗NP困难的方法。这个项目探索了它们的局限性，它的核心是一个证明独特的游戏猜想的程序。独特的博弈论猜想是近二十年来公认的逼近难的中心公开问题。它的求解将解决大量优化问题的逼近性问题，并证明几何技术的最优性。(1)解决唯一博弈猜想的布尔情形。研究人员正在与几何泛函分析和概率专家合作，以分析从NP-Hard问题到布尔唯一对策的归约。这种合作已经导致了一个里程碑，即从一个与NP-Hard问题相同精神的问题归结为布尔唯一游戏的分析。(2)证明了唯一对策猜想的布尔情形蕴含着完全的唯一对策猜想。研究人员正在开发技术，以“加强”硬布尔独特的游戏，以便它们允许强烈的平行重复和暗示独特的游戏猜想。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.