TR08-071 Authors: Dana Moshkovitz, Ran Raz

Publication: 6th August 2008 15:48

Downloads: 3689

Keywords:

We show that the NP-Complete language 3Sat has a PCP

verifier that makes two queries to a proof of almost-linear size

and achieves sub-constant probability of error $o(1)$. The

verifier performs only projection tests, meaning that the answer

to the first query determines at most one accepting answer to the

second query.

Previously, by the parallel repetition theorem, there were PCP

Theorems with two-query projection tests, but only (arbitrarily

small) constant error, and polynomial size.

There were also PCP Theorems with sub-constant error and

almost-linear size, but a constant number of queries that is

larger than $2$.

As a corollary, we obtain a host of new results. In particular,

our theorem improves many of the hardness of approximation

results that are proved using the parallel repetition theorem. A

partial list includes the following:

1) 3Sat cannot be efficiently approximated to within

a factor of 7/8+o(1), unless P=NP. This holds

even under almost-linear reductions. Previously, the best known

NP-hardness factor was 7/8+ epsilon for any

constant epsilon>0, under polynomial reductions

(by Hastad).

2) 3Lin cannot be efficiently approximated to within

a factor of 1/2+o(1), unless P=NP. This holds

even under almost-linear reductions. Previously, the best known

NP-hardness factor was 1/2+epsilon for any

constant epsilon>0, under polynomial reductions

(by Hastad).

3) A PCP Theorem with amortized query complexity 1 + o(1) and

amortized free bit complexity o(1). Previously, the best known

amortized query complexity and free bit complexity were

1+epsilon and epsilon, respectively, for any constant

epsilon > 0 (by Samorodnitsky and Trevisan).

One of the new ideas that we use is a new technique for doing the

composition step in the (classical) proof of the PCP

Theorem, without increasing the number of queries to the proof. We

formalize this as a composition of new objects that we call

Locally Decode/Reject Codes (LDRC). The notion of LDRC was

implicit in several previous works, and we make it explicit in

this work. We believe that the formulation of LDRCs and their

construction are of independent interest.