The Taub Faculty of Computer Science Events and Talks

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 composition.

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]