DIMACS Theory Seminar


"Reductions, Codes, PCPs, and Inapproximability"


Sanjeev Arora


Room 402, Computer Science Building,
Princeton University


Lunch 11:45 AM, Talk 12:10 PM
Friday, March 10, 1995


Recent results have shown that computing approximate solutions to several NP-hard optimization problems is NP-hard. But it is unclear what the limitations of these techniques are: Which inapproximability results can they not prove?

Our research addresses such questions. We identify a broad class of reductions -- namely, code-like reductions -- that includes all reductions used in known inapproximability results. We prove, under reasonable complexity assumptions, that code-like reductions cannot prove the hardness of approximating Clique within a factor $\sqrt{n}$, of approximating Vertex Cover within a factor 1.5, and of coloring a 3-colorable graph with $O(\log n)$ colors.

The above results help explain why it has been difficult to prove really good inapproximability result.

At the end, we will also argue that it is inherently difficult to come up with reductions that are not code-like. We provide some evidence supporting this view-point.

(The talk will be self-contained.)

Document last modified on March 7, 1995