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

IEEE Conference on Computational Complexity (CCC)

Error reduction by parallel repetition-a negative result

Uriel Feige, Oleg Verbitsky

Published Dec 23, 2002• 8 citations
Publisher

Abstract

We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz (1995), showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible.

DOI
10.1109/ccc.1996.507669

Related papers

Error reduction by parallel repetition-the state of the art

Uriel Feige

We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz, showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible. Our proof technique builds upon an idea of Oleg Verbitsky. We use this opportunity to survey the known results on parallel repetition, and to present the proofs of some previously claimed theorems. 1 Introduction A two prover one round proof system [8], MIP(2,1), is a protocol by which two provers jointly try to convince a computationally limited probabilistic verifier that a common input belongs to a prespecified language. The verifier selects a pair of questions at random. Each prover sees only one of the two questions, and sends back an answer. The verifier evaluates a predicate on the common input and the two questions and answers, and accepts or ...

•Nov 1, 1995•22 citations

Error reduction by parallel repetition - a negative result (Preliminary version)

Jriel Feigt

LVv slic-IW t,liat, iio fixed nriiribrr of parallel repetirdfices iir order to reduce t,lie error in tjwo-prover c.)iic~-roriiitl proof syst,eiiis from one constant. t,o another. Our resrilt,s imply t,liat> t,he recent bounds proven by Itail Raz, showing t,liat, tlir nuriiher of rorinds that, siiffice is inversely proport,ional t,o t,he answer length. iiw ticarly hest possihl?.

•Jan 1, 1996•1 citation

A Parallel Repetition Theorem

Ran Raz

We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].

SIAM Journal on Computing•Jan 1, 1998•703 citations

Two prover protocols

Uri 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 � .This upper bound depends only on p and on � (polynomial in 1/(1 − p) and in 1/� ).Based on previous work, it follows that for any �> 0, NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most � . As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1994•72 citations

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

A parallel repetition theorem

Ran Raz

We show that a parallel repetition of two-prover oneround proof systems (MIP(2, 1)) reduces the probability of error at an exponential rate.This settles a standing open problem, sometimes called 'The Parallel Repetition Conjecture".Previously, no constructive bound was known.The constant we have in the exponent is logarithmic in the total number of possible answers of the two provers.This is significantly better than what was previously known even in the much stmpler case where the questions to the two provers are chosen independently at random.In the most frequently used cases, our constant is just a global constant.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1995•81 citations
We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz (1995), showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible.
We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz, showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible. Our proof technique builds upon an idea of Oleg Verbitsky. We use this opportunity to survey the known results on parallel repetition, and to present the proofs of some previously claimed theorems. 1 Introduction A two prover one round proof system [8], MIP(2,1), is a protocol by which two provers jointly try to convince a computationally limited probabilistic verifier that a common input belongs to a prespecified language. The verifier selects a pair of questions at random. Each prover sees only one of the two questions, and sends back an answer. The verifier evaluates a predicate on the common input and the two questions and answers, and accepts or ...
We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].
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 � .This upper bound depends only on p and on � (polynomial in 1/(1 − p) and in 1/� ).Based on previous work, it follows that for any �> 0, NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most � . As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be 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.
We show that a parallel repetition of two-prover oneround proof systems (MIP(2, 1)) reduces the probability of error at an exponential rate.This settles a standing open problem, sometimes called 'The Parallel Repetition Conjecture".Previously, no constructive bound was known.The constant we have in the exponent is logarithmic in the total number of possible answers of the two provers.This is significantly better than what was previously known even in the much stmpler case where the questions to the two provers are chosen independently at random.In the most frequently used cases, our constant is just a global constant.