Derandomized Parallel Repetition of Structured PCPs
by Irit Dinur and Or Meir
Oded's comments
My personal view is that this work finally fulfills Muli Safra's
prophecy that low-error PCPs can be constructed
by combining derandomized parallel repetitions of PCPs
with derandomized Direct Product Tests (DPTs).
This prophecy was the trigger/kernel of our work
(in the mid 1990s), which was blocked both by the lack of
a good analysis of (derandomized) DPTs (as provided by IKW'09)
as well as by the difficulty of combining the structure of
a derandomized DPTs with the structure of the original PCP
that we wish to amplify.
The latter mismatch is removed by the current work, which shows that
any 2-query PCP can be restructured in a way that fits the structure
of the derandomized IKW'09 test. Specifically, the structure is
that the set of query pairs form a linear subspace.
The original abstract
A PCP is a proof system for NP in which the proof can be checked by a
probabilistic verifier. The verifier is only allowed to read a very small
portion of the proof, and in return is allowed to err with some bounded
probability. The probability that the verifier accepts a false proof is called
the soundness error, and is an important parameter of a PCP system that one
seeks to minimize. Constructing PCPs with sub-constant soundness error and, at
the same time, a minimal number of queries into the proof (namely two) is
especially important due to applications for inapproximability.
In this work we construct such PCP verifiers, i.e., PCPs that make only two
queries and have sub-constant soundness error. Our construction can be viewed
as a combinatorial alternative to the ``manifold vs. point" construction, which
is the only construction in the literature for this parameter range. The
``manifold vs. point" PCP is based on a low degree test, while our
construction is based on a direct product test. Our construction of a PCP is
based on extending the derandomized direct product test of Impagliazzo,
Kabanets and Wigderson (STOC 09) to a derandomized parallel repetition theorem.
More accurately, our PCP construction is obtained in two steps. We first prove
a derandomized parallel repetition theorem for specially structured PCPs. Then,
we show that any PCP can be transformed into one that has the required
structure, by embedding it on a de-Bruijn graph.
Back to
list of Oded's choices.