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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Sanjeev Arora , Carsten Lund (1996). Hardness of Approximations. PW Publishing.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy (1998) Proof verification and Intractability of Approximation Problems. Journal of ACM 45(3): 501–555 Preliminary version in FOCS 1992
Sanjeev Arora, Shmuel Safra (1998) Probabilistic Checkable Proofs: A New Characterization of NP. Journal of ACM volume 45(1): 70–122 Preliminary version in FOCS 1992
Sanjeev Arora, Madhu Sudan (2003) Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365–426
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy (1991). Checking Computations in Polylogarithmic Time. In STOC, 21–31
Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell (1993). Efficient probabilistically checkable proofs and applications to approximations. In STOC, 294–304.
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan (2006) Robust PCPs of Proximity, Shorter PCPs and Applications to Coding. SIAM Journal of Computing 36(4): 120–134
Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah (2009). Sound 3-Query PCPPs Are Long. TOCT 1(2).
Peter J. Cameron (1998) Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge CB2 2RU, MA, USA
Irit Dinur (2007) The PCP Theorem by Gap Amplification. Journal of ACM 54(3): 241–250 Preliminary version in STOC 2006
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra (1999). PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. In STOC, 29–40.
Irit Dinur, Elazar Goldenberg (2008). Locally Testing Direct Product in the Low Error Range. In FOCS, 613–622.
Irit Dinur, Praladh Harsha (2009). Composition of low-error 2-query PCPs using decodable PCPs. In FOCS.
Irit Dinur, Or Meir (2010). Derandomized Parallel Repetition via Structured PCPs. In CCC.
Irit Dinur, Omer Reingold (2006) Assignment testers: Towards combinatorial proof of the PCP theorem. SIAM Journal of Computing 36(4): 155–164
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy (1996) Interactive Proofs and the Hardness of Approximating Cliques. J. ACM 43(2): 268–292
Uriel Feige, Joe Kilian (1995). Impossibility results for recycling random bits in two-prover proof systems. In STOC, 457–468.
Oded Goldreich, Shmuel Safra (2000) A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. SIAM J. Comput. 29(4): 1132–1154
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson (2008). Uniform direct product theorems: simplified, optimized, and derandomized. In STOC, 579–588.
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson (2009). New direct-product testers and 2-query PCPs. In STOC, 131–140.
Subhash Khot (2006) Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. SIAM J. Comput. 36(4): 1025–1071
Thomson Leighton F. (1992) Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA
Alexander Lubotzky, R. Phillips, P. Sarnak (1988) Ramanujan graphs. Combinatorica 8(3): 261–277
Or Meir (2009). Combinatorial PCPs with efficient verifiers. In FOCS.
Dana Moshkovitz, Ran Raz (2008). Two Query PCP with Sub-Constant Error. In FOCS. Full version is available as ECCC TR08-071.
Christos H. Papadimitriou, Mihalis Yannakakis (1991) Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43(3): 425–440
Alexander Polishchuk, Daniel A. Spielman (1994). Nearly- linear size holographic proofs. In STOC, 194–203.
Ran Raz (1998) A Parallel Repetition Theorem. SIAM J. Comput. 27(3): 763–803
Ran Raz, Shmuel Safra (1997). A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In STOC, 475–484.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Dinur, I., Meir, O. Derandomized Parallel Repetition via Structured PCPs. comput. complex. 20, 207–327 (2011). https://doi.org/10.1007/s00037-011-0013-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-011-0013-5