CAREER: Optimal Approximability

PI提出研究max - cut、Max-2-Sat、Vertex-Cover、Chromatic-Number等约束满足问题。对于许多这样的问题，有效可实现的近似比和NP-hard近似比之间的界限是未知的。pi有一个3点计划来确定这些边界：使用半确定编程算法，完整性缺口和属性测试之间的最近联系来确定精确的边界，假设“唯一游戏猜想”。定义和探索新的、更有效的基于性能测试的硬度降低方法。使用新的基于属性测试的约简以及平行重复理论的想法来证明唯一游戏猜想。这条研究路线的更广泛目标是为基本算法任务（如网络划分，约束满足和优化）提供更高效和更有效的算法。PI将探索有效算法解决这些问题的极限。证明“硬性结果”或对有效计算能力的限制具有积极的实际影响。首先，它可以防止在试图改进无法改进的算法上浪费精力。更重要的是，通过仔细地隔离算法任务中使它们变得困难的方面，我们通常会在这些方面不存在的情况下找到新的、有效的算法来解决任务。

The PI proposes to study constraint satisfaction problems likeMax-Cut, Max-2-Sat, Vertex-Cover, and Chromatic-Number. For many ofthese problems, the boundary between efficiently-achievableapproximation ratios and NP-hard approximation ratios is unknown. ThePI has a 3-point plan to determine these boundaries:1. Use recent connections between semidefinite programming algorithms,integrality gaps, and property testing to determine preciseboundaries, assuming the "Unique Games Conjecture."2. Define and explore new, more efficient property-testing--basedhardness reductions.3. Prove the Unique Games Conjecture, using the newproperty-testing--based reductions along with ideas from the theory ofParallel Repetition.The broader goal of this line of research is to give more efficientand more effective algorithms for the fundamental algorithmic taskslike network partitioning, constraint satisfaction, and optimization.The PI will explore the limits of how well efficient algorithms cansolve these problems. Proving "hardness results" or limitations onthe capabilities of efficient computation has positive practicalconsequences. For one, it prevents wasted effort in trying to improveunimprovable algorithms. More importantly, by carefully isolating theaspects of algorithmic tasks which make them difficult, we are oftenled to new, effective algorithms for solving the tasks when theseaspects are not present.