Composition of low-error 2-query PCPs using decodable PCPs

by Irit Dinur and Prahladh Harsha

Oded's comments

The abstract is quite long and does a good job explaining the context of this work, so I guess I need add nothing. Actually, let me seize the oppertunity to express my opinion that the most important aspect of [MR08b] is achieving almost-linear length PCP of arbitrary small constant error rather than making this small error vanish (i.e., be sub-constant). In fact, obtaining a fixed polynomial length for an arbitrary small constant error would have been interesting too.
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.

The original abstract

Proof composition, introduced in [AS98], is an essential ingredient in all known constructions of probabilistically checkable proofs (PCPs). By now, modular composition theorems are known [BGH+06, DR06], but only in the constant soundness error regime. These theorems have led to better understanding of PCPs, resulting in alternate proofs of the PCP Theorem, and construction of shorter PCPs [BGH+06, DR06, BS08, Din08].
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.