CAREER: Challenges in Hardness of Approximation

人类感兴趣的许多优化问题都是NP难的，人们普遍认为没有有效的算法。这包括从运筹学和经济学到物理学、化学、生物学和神经科学等领域的问题。即使是近似的NP难问题通常也是NP难的，但是如此严格地证明是一项困难的任务，这-通过思想的飞跃-导致了关于证明的性质及其验证的基本问题。虽然这种联系和近似的NP难性的第一个证明是在20世纪90年代发现的，但即使是20多年后的今天，有关证明检查和近似难性的一些最困难的问题仍然悬而未决。该项目试图回答诸如Bellare、Goldwasser、隆德和Russell的滑动尺度猜想以及Khot的独特博弈猜想等核心和困难的问题。滑尺猜想及其变体意味着有向稀疏割和最接近向量问题的最佳逼近难度。唯一博弈猜想暗示了顶点覆盖和最大割等问题的最优逼近难度，也预测了基本半定规划技术对广泛问题族的最优性。 关于滑动尺度猜想，该项目包括四条攻击线：通过代数，通过去随机化的平行重复，通过组合和通过算法（可能的反驳）。关于独特的游戏猜想，该项目侧重于一个新的和有前途的攻击线，涉及一个新的编码方案称为真实的代码。该项目中考虑的许多问题的兴趣远远超出了PCP的预期应用，例如几何学，或者在并行重复的情况下，密码学，通信复杂性和量子计算。 研究生和本科生都将参加这项研究活动。

Many of the optimization problems of interest to humanity are NP-hard and widely believed not to have efficient algorithms. This includes problems in fields ranging from operations research and economics to physics, chemistry, biology and neuroscience. Even approximating NP-hard problems is often NP-hard, but proving so rigorously is a difficult task, which - by a leap of thought - leads to fundamental questions about the nature of proofs and their verification. While this connection and the first proofs of NP-hardness of approximation were discovered in the 1990's, even now, more than 20 years later, some of the most difficult questions about checking of proofs and hardness of approximation remain open.This project attempts to answer such central and difficult questions as the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell and the Unique Games Conjecture of Khot. The Sliding Scale Conjecture and its variants imply optimal hardness of approximation for problems like Directed-Sparsest-Cut and Closest-Vector-Problem. The Unique Games Conjecture implies optimal hardness of approximation for problems like Vertex-Cover and Max-Cut, as well predicts the optimality of basic semidefinite programming techniques for wide families of problems. Regarding the Sliding Scale Conjecture, the project includes four lines of attack: through algebra, through derandomized parallel repetition, through composition and through algorithms (possible refutations). Regarding the Unique Games Conjecture, the project focuses on a new and promising line of attack that involves a new encoding scheme called the real code. Many of the problems considered in the project are of interest well beyond their intended applications for PCP, for example, to geometry, or, in the case of parallel repetition, to cryptography, communication complexity and quantum computing. Both graduate and undergraduate students would participate in this research activities.