Title: Two Query PCP with Sub-Constant Error
Speaker: Dana Moshkovitz, Princeton
Abstract:
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+e for any constant
e>0, under polynomial reductions (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+e for any constant e>0, under polynomial
reductions (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+e and e, respectively, for any constant e>0
(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.
This is joint work with Ran Raz