The Taub Faculty of Computer Science Events and Talks
Prahladh Harsha (UT Austin & Technion)
Wednesday, 25.03.2009, 15:00
In a recent breakthrough, Moshkovitz and Raz [MR] proved that NP can be
verified using two queries, sub-constant error, and nearly linear
proof length. The main technical component of their result is a new
composition theorem for certain specific 2-query PCPs. All earlier
composition theorems suffered from incurring an additional query per
We abstract their proof and prove a generic 2-query PCP composition
theorem with low error. More formally, we define a certain (natural)
type of PCP verifier and show how to compose such verifiers without
incurring an extra query. Our composition works regardless of the way
the verifiers themselves are constructed.
This composition theorem is then used to give a simpler
and modular proof of the results of [MR] mentioned above. This is done
by an iterative application of the composition theorem, using known
components (namely, the "folklore" manifold vs. point construction).
Our construction suffers from the same bottleneck as [MR] with respect
to the error probability, in that, it is inverse polynomial (not
exponential) in the alphabet size.
[Joint work with Irit Dinur]