New techniques for probabilistically checkable proofs and inapproximability results
Sanjeev Arora, Subhash Khot · 2003
Certain NP-hard problems like Clique and MAX-3SAT have resisted all attempts to find non-trivial approximation. Is there any inherent reason for the apparent inapproximability of these problems? The discovery of PCP Theorem and subsequent research have shown that for Clique and MAX-3SAT, any non-trivial approximation is as hard as finding the exact solution! In this work, we continue this line of research and show inapproximability of many fundamental NP-hard problems. These include (Hyper-)Graph Coloring, Shortest Vector Problem (SVP) in lattices, Hypergraph Vertex Cover, Clique and Chromatic Number of graphs, and some results based on the Unique Games Conjecture (UGC) that we propose. Specifically, we show that: (Hyper-)Graph Coloring: It is hard to color (i) k-colorable graphs with kΩ(log k ) colors, (ii) 3-colorable 3-uniform hypergraphs with (log log n)Ω(1) colors, and (iii) k-colorable 4-uniform hypergraphs with (log n)Ω(k ) colors. SVP: For all large enough p, it is hard to find the shortest nonzero vector in an n-dimensional lattice under Lp norm within factor p 1-o(1). Hypergraph Vertex Cover: The vertex cover in k-uniform hypergraphs is hard to approximate within factor k − 1 − o(1) for every k ≥ 3. Clique and Chromatic Number of Graphs: Both these problems are hard to approximate within factor n2log ng for some constant g < 1. Consequences of UGC: We propose a conjecture about certain 2-Prover-1-Round games and show that it implies any constant factor hardness for Min-2SAT Deletion and factor k − o(1) hardness for vertex cover in k-uniform hypergraphs for every k ≥ 2. We use the powerful machinery of Probabilistically Checkable Proofs and introduce many new techniques for constructing and analyzing PCPs.