CAREER: Challenges in Hardness of Approximation

点击翻译按钮获取中文摘要

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.