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.