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