Title: 2-query PCP Composition
Speaker: Irit Dinur, Weizmann Institute of Science.
Abstract:
In a recent breakthrough, Moshkovitz and Raz 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 prove a general 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 "plug-and-play" proof of the results of [MR]
mentioned above. This is done by an iterative application of the composition theorem, starting from 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 length.
Joint work with Prahladh Harsha