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

Error reduction by parallel repetition-the state of the art

Uriel Feige

Published Nov 1, 1995• 22 citations
OpenAlex

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, 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 ...

Related papers

Error reduction by parallel repetition-a negative result

Uriel Feige, Oleg Verbitsky

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.

IEEE Conference on Computational Complexity (CCC)•Dec 23, 2002•8 citations

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

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

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

An Efficient Concurrent Repetition Theorem.

Douglas Wikström

H˚astad et al. (2008) prove, using Raz’s lemma (STOC ’95) the first efficient parallel repetition theorem for protocols with a non-constant number of rounds, for a natural generalization of public-coin protocols. They show that a parallel prover that convinces a fraction 1 − γ of the embedded verifiers of a k-wise repeated m-message verifier can be turned into a prover with error probability 1 − γ − O(m √ − log (ɛ) /k). This improves previous results of Impagliazzo et al. (Crypto 2007) and Pass and Venkitasubramaniam (STOC 2007) that studies the constant round case. We prove a generalization of Raz’s Lemma to random processes that allows us to improve the analysis of the reduction of H˚astad et al. in the public-coin case to 1 − γ − O ( √ − log (ɛ) /k), i.e., we remove the dependence on the number rounds completely, and thus the restriction to settings where k> m2. An important implication of the strengthened parallel repetition theorem is the first efficient concurrent repetition theorem for protocols with a non-constant number of rounds. In concurrent repetition, the verifiers execute completely independently and only report their final decision, i.e., the prover chooses arbitrarily in which order it interacts with the individual verifiers. This should be contrasted with parallel repetition where the verifiers are synchronized in each round. 1

•Jan 1, 2009•3 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, 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 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.
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.
H˚astad et al. (2008) prove, using Raz’s lemma (STOC ’95) the first efficient parallel repetition theorem for protocols with a non-constant number of rounds, for a natural generalization of public-coin protocols. They show that a parallel prover that convinces a fraction 1 − γ of the embedded verifiers of a k-wise repeated m-message verifier can be turned into a prover with error probability 1 − γ − O(m √ − log (ɛ) /k). This improves previous results of Impagliazzo et al. (Crypto 2007) and Pass and Venkitasubramaniam (STOC 2007) that studies the constant round case. We prove a generalization of Raz’s Lemma to random processes that allows us to improve the analysis of the reduction of H˚astad et al. in the public-coin case to 1 − γ − O ( √ − log (ɛ) /k), i.e., we remove the dependence on the number rounds completely, and thus the restriction to settings where k> m2. An important implication of the strengthened parallel repetition theorem is the first efficient concurrent repetition theorem for protocols with a non-constant number of rounds. In concurrent repetition, the verifiers execute completely independently and only report their final decision, i.e., the prover chooses arbitrarily in which order it interacts with the individual verifiers. This should be contrasted with parallel repetition where the verifiers are synchronized in each round. 1