New Techniques for Probabilistically Checkable Proofs and Inapproximability Results (Thesis)
Report ID: TR-673-03Author: Khot, Subhash A.
Date: 2003-08-00
Pages: 246
Download Formats: |PDF| |Postscript|
Abstract:
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^{\Omega(\log k)} colors, (ii) 3-colorable 3-uniform hypergraphs with
(\log \log n)^{\Omega(1)} colors, and (iii) k-colorable 4-uniform hypergraphs
with (\log n)^{\Omega(k)} colors.
SVP : For all large enough p, it is hard to find the shortest nonzero vector
in an n-dimensional lattice under L_p 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 \frac{n}{2^{(\logn)^\gamma}} for some constant
\gamma < 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.