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.