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

International Journal of Foundations of Computer Science

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

Oleg Verbitsky

Published Aug 1, 2001• 0 citations
Publisher

Abstract

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.

DOI
10.1142/s012905410100062x

Related papers

A k-PROVERS PARALLEL REPETITION THEOREM FOR A VERSION OF NO-SIGNALING MODEL

Ricky Rosen

The parallel repetition theorem states that for any two provers one round game with value at most 1 - ∊ (for ∊ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∊3)Ω(n/ log s) where s is the size of the answers set [9, 12]. It is not known how the value of the game decreases when there are three or more players. In this paper we address the problem of the error decrease of parallel repetition game for k-provers where k > 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k-provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.

Discrete Mathematics Algorithms and Applications•Dec 1, 2010•0 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

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

Parallel Repetition of Prover-Verifier Quantum Interactions

Abel Molina

In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. \n \nWe first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. \n \nWe look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. \n \nFinally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

•Jan 1, 2011•0 citations

Does parallel repetition lower the error in computationally sound protocols?

Mihir Bellare Y, Russell Impagliazzo, Moni Naor

Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•114 citations
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.
The parallel repetition theorem states that for any two provers one round game with value at most 1 - ∊ (for ∊ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∊3)Ω(n/ log s) where s is the size of the answers set [9, 12]. It is not known how the value of the game decreases when there are three or more players. In this paper we address the problem of the error decrease of parallel repetition game for k-provers where k > 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k-provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.
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 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 ...
In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. \n \nWe first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. \n \nWe look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. \n \nFinally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.
Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.