Regarding the proof of the result: The actual presentation proceeds in terms of (highly) robust PCPs, while relying on the equivalence of the latter to two-query PCPs. Indeed, this equivalence is another contribution of the paper. As for the composition of robust PCPs it starts by observing that there is no need to keep the outer proof for consistency, since consistency can be tested by comparing two related inner proofs (which refer to the same position in the outer proof). This, however, changes nothing because still consistency can be achieved by modifying less than half of the total length of both scanned parts. The new idea is to check consistency among $d$ such parts, which may allow to reduce robustness error to approximately $1/d$. Indeed, this is doable, and is what the new composition theorem does. Note that the above description relies on the fact that the inner PCP is decodable.

In contrast, a similar understanding of PCP composition in the low soundness error regime has been lacking. The existing composition methods are non-modular (i.e., composition is very much tailored to the specific PCPs that are composed in an ad-hoc fashion), resulting in complicated constructions of PCPs. Furthermore, until recently, composition in the low soundness error regime suffered from incurring an extra "consistency" query, resulting in a PCP that is not "two-query" and hence, much less useful for hardness-of-approximation reductions. In a recent breakthrough, Moshkovitz and Raz [MR08b] constructed almost linear-sized low-error 2-query PCPs for every language in NP. The main technical component of their construction is a composition technique, which however is fairly involved and works only for certain specific 2-query PCPs.

The main result of this paper is a surprisingly simple, yet generic, composition theorem for low error two-query PCPs. Towards this end, we introduce a new variant of PCP, which we call a decodable PCP (dPCP). A dPCP is an encoding of an NP witness that is both checkable and decodable. The dPCP verifier in addition to verifying the validity of the given proof like a standard PCP verifier, also locally decodes the original NP witness. Our composition is generic in the sense that it works regardless of the way the component PCPs are constructed.

By repeatedly applying the new composition theorem to known components, we give a considerably simpler and modular proof of the result of [MR08b]. However, our construction has the same bottleneck as [MR08b] with respect to the error probability, in that, it is inverse logarithmic (not polynomial) in the alphabet size.

Back to list of Oded's choices.