Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Annual Symposium on Foundations of Computer Science

Two Query PCP with Sub-Constant Error

Dana Moshkovitz, Ran Raz

Published Jun 25, 2008• 186 citations
Publisher

Abstract

We show that the NP-Complete language 3Sat has a PCPverifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query.Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size.There were also PCP Theorems with sub-constant error andalmost-linear size, but a constant number of queries that is larger than 2.As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following:(1) 3Sat cannot be efficiently approximated to withina factor of 7/8+o(1), unless P = NP. This holds even under almost-linear reductions. Previously, the best knownNP-hardness factor was 7/8+epsilon for any constant epsilonGt0, under polynomial reductions.(2) 3Lin cannot be efficiently approximated to withina factor of 1/2+o(1), unless P = NP. This holdseven under almost-linear reductions. Previously, the best known NP-hardness factor was 1/2+epsilon for any constant epsilonGt0, under polynomial reductions.(3) A PCP Theorem with amortized query complexity 1 + o(1)and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1+epsilon and epsilon, respectively, for any constant epsilon Gt 0.One of the new ideas that we use is a new technique for doing the composition step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call Locally Decode/Reject Codes (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.

DOI
10.1109/focs.2008.60

Related papers

Two-Prover Protocols---Low Error at Affordable Rates

Uriel Feige, Joe Kilian

We introduce the miss-match form for two-prover one-round proof systems. Any two-prover one-round proof system can be easily modified so as to be in miss-match form. Proof systems in miss-match form have the "projection" property that is important for deriving hardness of approximation results for NP-hard combinatorial optimization problems. Our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to $\epsilon$. This upper bound depends only on p and on $\epsilon$ (polynomial in 1/(1-p) and in $1/\epsilon$). Based on previous work, it follows that for any $\epsilon >0,$ NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most $\epsilon$. As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.

SIAM Journal on Computing•Jan 1, 2000•35 citations

Parallel Repetition from Fortification

Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and short. As corollaries, we obtain: (1) Starting from a PCP Theorem with soundness error bounded away from 1, we get a PCP with arbitrarily small constant soundness error. In particular, starting with the combinatorial PCP of Dinur, we get a combinatorial PCP with low error. The latter can be used for hardness of approximation as in the work of Håstad. (2) Starting from the work of the author and Raz, we get a projection PCP theorem with the smallest soundness error known today. The theorem yields nearly a quadratic improvement in the size compared to previous work. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error.

Annual Symposium on Foundations of Computer Science•Oct 1, 2014•13 citations

Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist.

Gillat Kol, Ran Raz

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC predicts that such PCP verifiers can have almost-perfect completeness and low-soundness. The computational complexity notion of a PCP is closely related to the combinatorial notion of a Locally Testable Code (LTC). LTCs are error-correcting codes with codeword testers that only make a constant number of queries to the tested word. All known PCP constructions use LTCs as building blocks. Furthermore, to obtain PCPs with certain properties, one uses LTCs with corresponding properties. In light of the strong connection between PCPs and LTCs, one may conjecture the existence of LTCs with properties similar to the ones required by the UGC. In this work we show that such LTCs do not exist. That is, we consider 2-query LTCs with codeword testers that only make unique tests. Roughly speaking, we show that any such LTC with relative distance close to 1, almost-perfect completeness and low-soundness, is of constant size. The result intends to point out the limitations of the current techniques for constructing PCPs. It suggests that proving the UGC may require a new approach.

Electronic colloquium on computational complexity•Jan 1, 2009•3 citations

Parallel Repetition of Fortified Games.

Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G⊗k in terms of the value of the game G and the number of repetitions k. Contrary to what one might have guessed, the value of G⊗k is not val(G), but rather a more complicated expression depending on properties of G. Indeed, there are numerous works aiming to understand the value of repeated games, both for general games G and for special cases. A case of particular interest is that of projection games, where the answer of the first prover determines at most one acceptable answer for the second prover. In this work we give a simple transformation, which we call “fortification”, that can be applied to any projection game. We show that for fortified games G, the value of the k-repeated game is approximately val(G). This results in nearly a quadratic improvement in the size of projection PCP with the lowest error known today. Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. ∗dmoshkov@csail.mit.edu. Department of Electrical Engineering and Computer Science, MIT. This material is based upon work supported by the National Science Foundation under Grant Number 1218547.

Electronic colloquium on computational complexity•Jan 1, 2014•1 citation

REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM

Oleg Verbitsky

The Parallel Repetition Theorem says that n-fold parallel execution of a two-prover one-round interactive proof system reduces the error probability exponentially in n. The bound on the error probability of the parallelized system depends on the error probability and the answer size of the single proof system. It is still unknown whether the theorem holds true with a bound depending only on the query size. This kind of a bound may be preferable whenever the query size is considerably smaller than the answer size, what really happens in some cryptographic protocols. Such a bound is only known in the case that queries to the provers are independent. The present paper extends this result to some cases of strong correlation between queries. In particular, a query-based variant of the Parallel Repetition Theorem is proven when the graph of dependence between queries to the provers is a tree and, in a bit weaker form, when this graph is a cycle.

International Journal of Foundations of Computer Science•Aug 1, 2001•0 citations

Classical versus quantum queries in quantum PCPs with classical proofs

Harry Buhrman, François Le Gall, Jordi R. Weggemans

We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for $q$ quantum queries to a polynomially-sized classical proof ($\mathsf{QCPCP}_{Q,c,s}[q]$). Exploiting a connection with the polynomial method, we prove that for any constant $q$, promise gap $c-s = Ω(1/\text{poly}(n))$ and $δ>0$, we have $\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-δ,1/2+δ}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, where $\mathsf{BQ} \cdot \mathsf{NP}$ is the class of promise problems with quantum reductions to an $\mathsf{NP}$-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $\mathsf{QCMA}$, as it is unlikely that $\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer $c$, there exists an oracle relative to which $\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]$, contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.

arXiv:2411.00946•Nov 1, 2024•0 citations
We show that the NP-Complete language 3Sat has a PCPverifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query.Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size.There were also PCP Theorems with sub-constant error andalmost-linear size, but a constant number of queries that is larger than 2.As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following:(1) 3Sat cannot be efficiently approximated to withina factor of 7/8+o(1), unless P = NP. This holds even under almost-linear reductions. Previously, the best knownNP-hardness factor was 7/8+epsilon for any constant epsilonGt0, under polynomial reductions.(2) 3Lin cannot be efficiently approximated to withina factor of 1/2+o(1), unless P = NP. This holdseven under almost-linear reductions. Previously, the best known NP-hardness factor was 1/2+epsilon for any constant epsilonGt0, under polynomial reductions.(3) A PCP Theorem with amortized query complexity 1 + o(1)and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1+epsilon and epsilon, respectively, for any constant epsilon Gt 0.One of the new ideas that we use is a new technique for doing the composition step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call Locally Decode/Reject Codes (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.
We introduce the miss-match form for two-prover one-round proof systems. Any two-prover one-round proof system can be easily modified so as to be in miss-match form. Proof systems in miss-match form have the "projection" property that is important for deriving hardness of approximation results for NP-hard combinatorial optimization problems. Our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to ϵ\epsilonϵ. This upper bound depends only on p and on ϵ\epsilonϵ (polynomial in 1/(1-p) and in 1/ϵ1/\epsilon1/ϵ). Based on previous work, it follows that for any ϵ>0,\epsilon >0,ϵ>0, NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most ϵ\epsilonϵ. As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.
The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and short. As corollaries, we obtain: (1) Starting from a PCP Theorem with soundness error bounded away from 1, we get a PCP with arbitrarily small constant soundness error. In particular, starting with the combinatorial PCP of Dinur, we get a combinatorial PCP with low error. The latter can be used for hardness of approximation as in the work of Håstad. (2) Starting from the work of the author and Raz, we get a projection PCP theorem with the smallest soundness error known today. The theorem yields nearly a quadratic improvement in the size compared to previous work. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error.
The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC predicts that such PCP verifiers can have almost-perfect completeness and low-soundness. The computational complexity notion of a PCP is closely related to the combinatorial notion of a Locally Testable Code (LTC). LTCs are error-correcting codes with codeword testers that only make a constant number of queries to the tested word. All known PCP constructions use LTCs as building blocks. Furthermore, to obtain PCPs with certain properties, one uses LTCs with corresponding properties. In light of the strong connection between PCPs and LTCs, one may conjecture the existence of LTCs with properties similar to the ones required by the UGC. In this work we show that such LTCs do not exist. That is, we consider 2-query LTCs with codeword testers that only make unique tests. Roughly speaking, we show that any such LTC with relative distance close to 1, almost-perfect completeness and low-soundness, is of constant size. The result intends to point out the limitations of the current techniques for constructing PCPs. It suggests that proving the UGC may require a new approach.
The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G⊗k in terms of the value of the game G and the number of repetitions k. Contrary to what one might have guessed, the value of G⊗k is not val(G), but rather a more complicated expression depending on properties of G. Indeed, there are numerous works aiming to understand the value of repeated games, both for general games G and for special cases. A case of particular interest is that of projection games, where the answer of the first prover determines at most one acceptable answer for the second prover. In this work we give a simple transformation, which we call “fortification”, that can be applied to any projection game. We show that for fortified games G, the value of the k-repeated game is approximately val(G). This results in nearly a quadratic improvement in the size of projection PCP with the lowest error known today. Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. ∗dmoshkov@csail.mit.edu. Department of Electrical Engineering and Computer Science, MIT. This material is based upon work supported by the National Science Foundation under Grant Number 1218547.
The Parallel Repetition Theorem says that n-fold parallel execution of a two-prover one-round interactive proof system reduces the error probability exponentially in n. The bound on the error probability of the parallelized system depends on the error probability and the answer size of the single proof system. It is still unknown whether the theorem holds true with a bound depending only on the query size. This kind of a bound may be preferable whenever the query size is considerably smaller than the answer size, what really happens in some cryptographic protocols. Such a bound is only known in the case that queries to the provers are independent. The present paper extends this result to some cases of strong correlation between queries. In particular, a query-based variant of the Parallel Repetition Theorem is proven when the graph of dependence between queries to the provers is a tree and, in a bit weaker form, when this graph is a cycle.
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for qqq quantum queries to a polynomially-sized classical proof (QCPCPQ,c,s[q]\mathsf{QCPCP}_{Q,c,s}[q]QCPCPQ,c,s​[q]). Exploiting a connection with the polynomial method, we prove that for any constant qqq, promise gap c−s=Ω(1/poly(n))c-s = Ω(1/\text{poly}(n))c−s=Ω(1/poly(n)) and δ>0δ>0δ>0, we have QCPCPQ,c,s[q]⊆QCPCP1−δ,1/2+δ[3]⊆BQ⋅NP\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-δ,1/2+δ}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}QCPCPQ,c,s​[q]⊆QCPCP1−δ,1/2+δ​[3]⊆BQ⋅NP, where BQ⋅NP\mathsf{BQ} \cdot \mathsf{NP}BQ⋅NP is the class of promise problems with quantum reductions to an NP\mathsf{NP}NP-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for QCMA\mathsf{QCMA}QCMA, as it is unlikely that QCMA⊆BQ⋅NP\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{NP}QCMA⊆BQ⋅NP, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer ccc, there exists an oracle relative to which QCPCP[O(log⁡cn)]⊊QCPCPQ[O(log⁡cn)]\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]QCPCP[O(logcn)]⊊QCPCPQ​[O(logcn)], contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.