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

AF：小：独特的博弈猜想及近似难度中的相关问题

• 批准号: 2200956
• 负责人: Dana Moshkovitz
• 金额: $ 60万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-04-15 至 2025-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2200956&HistoricalAwards=false
• 关键词: AF; Small; Unique; Games; Conjecture

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.

许多优化问题是NP硬化，因此不太可能具有有效的算法。迄今为止，近似算法通常基于线性和半决赛编程等几何技术，是针对NP硬度的最成功的方法。该项目探讨了他们的局限性，其内心是一个朝着独特游戏猜想的证明的计划。 在过去的二十年中，独特的游戏猜想被广泛认为是近似硬度的核心开放问题。它的解决方案将解决大量优化问题的近似性，并证明几何技术的最佳性。上述针对独特游戏的程序由两个独立的组件组成。 （1）解决独特游戏猜想的布尔案例。研究人员正在与几何功能分析和概率方面的专家合作，以分析从NP硬性问题减少到布尔值独特游戏。这项合作已经导致了一个里程碑，即对与NP-HARD问题相同的精神减少问题的分析来分析布尔独特的游戏。 （2）表明独特游戏的布尔案例猜想意味着完整的独特游戏猜想。研究人员正在开发“强化”硬布尔独特游戏的技术，因此他们承认强大的平行重复，并暗示了独特的游戏猜想。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来评估的支持。

项目成果

Efficient Interactive Proofs for Non-Deterministic Bounded Space

非确定性有界空间的高效交互式证明

• DOI: 10.4230/lipics.approx/random.2023.47
• 发表时间: 2023
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023
• 作者: Cook, Joshua;Rothblum, Ron D.
• 通讯作者: Rothblum, Ron D.

Regularization of Low Error PCPs and an Application to MCSP

低误差 PCP 的正则化及其在 MCSP 中的应用

• DOI: 10.4230/lipics.isaac.2023.39
• 发表时间: 2023
• 期刊: 34th International Symposium on Algorithms and Computation (ISAAC 2023
• 作者: Hirahara, Shuichi;Moshkovitz, Dana
• 通讯作者: Moshkovitz, Dana

Almost Chor-Goldreich Sources and Adversarial Random Walks

• DOI: 10.1145/3564246.3585134
• 发表时间: 2023-06
• 期刊: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Dean Doron;Dana Moshkovitz;Justin Oh;David Zuckerman

Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE

PSPACE 验证者高效 PCP 提供更严格的 MA/1 电路下限

• DOI: 10.4230/lipics.approx/random.2023.55
• 发表时间: 2024
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023
• 作者: Cook, Joshua;Moshkovitz, Dana
• 通讯作者: Moshkovitz, Dana