Paper Info
Title
Derandomized Parallel Repetition via Structured PCPs
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 proof of a false claim is called the soundness error and is an important parameter of a PCP system that one seeks to minimize. Constructing PCPs with subconstant 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 subconstant soundness error. Our construction can be viewed as a combinatorial alternative to the “manifold vs. point” construction, which is the basis for all constructions 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. We also extend our construction to yield a decodable PCP (dPCP) with the same parameters. By plugging in this dPCP into the scheme of Dinur and Harsha (FOCS 2009), one gets an alternative construction of the result of Moshkovitz and Raz (FOCS 2008), namely a construction of two-query PCPs with small soundness error and small alphabet size. 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.
Year
DOI
Venue
2011
10.1007/s00037-011-0013-5
Computational Complexity - Selected papers from the 25th Annual IEEE Conference on Computational Complexity (CCC 2010)
Keywords
DocType
Volume
PCP, low error, de-Bruijn, direct product, direct product test, derandomized parallel repetition, 68Q15
Journal
20
Issue
ISSN
Citations 
2
1420-8954
16
PageRank 
References 
Authors
0.74
27
2
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Or Meir26610.47