CAREER: Challenges in Hardness of Approximation

人类感兴趣的许多优化问题都是np困难的，人们普遍认为没有有效的算法。这包括从运筹学和经济学到物理、化学、生物学和神经科学等领域的问题。即使是近似np困难的问题也常常是np困难的，但如此严格地证明是一项艰巨的任务，这——通过思想的飞跃——导致了关于证明及其验证的本质的基本问题。虽然这种联系和np -逼近硬度的第一个证明是在20世纪90年代发现的，但即使在20多年后的今天，关于检验证明和逼近硬度的一些最困难的问题仍然没有解决。这个项目试图回答诸如Bellare， Goldwasser， Lund和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.