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

Lecture notes in computer science

Parallel repetition of MIP(2,1) systems

Clemens Gröpl, Martin Skutella

Published Jan 1, 1998• 0 citations
Publisher
DOI
10.1007/bfb0053016

Related papers

An Efficient Parallel Repetition Theorem

Johan Håstad, Rafael Pass, Douglas Wikström +1 more

Lecture notes in computer science•Jan 1, 2010•46 citations

Error Reduction by Parallel Repetition—A Negative Result

Uriel Feige, Oleg Verbitsky

COMBINATORICA•Oct 1, 2002•36 citations

Two-prover one-round proof systems: their power and their problems (extended abstract)

Uriel Feige, László Lovász

We characterize the power of two-prover one-round (MIP(2,1)) proof systems, showing that MIP(2,1)=NEXPTIME. However, the following intriguing question remains open: Does parallel repetition decrease the error probability of MIP(2,1) proof systems?.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1992•177 citations

No-Signaling MIPs and Faster-Than-Light Communication, Revisited.

Justin Holmgren

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

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•87 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•724 citations
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 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].