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 - a negative result (Preliminary version)

Jriel Feigt

Published Jan 1, 1996• 1 citation
OpenAlex

Abstract

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

Related papers

Error Reduction by Parallel Repetition—A Negative Result

Uriel Feige, Oleg Verbitsky

COMBINATORICA•Oct 1, 2002•36 citations

A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model

Ricky Rosen

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

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

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•23 citations

On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG.

Young Kun Ko

Electronic colloquium on computational complexity•Jan 1, 2018•0 citations

On Parallel Repetition of Interactive Proof Systems

Oded Goldreich

Lecture notes in computer science•Jan 1, 2025•1 citation
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?.
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 ...