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

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—A Negative Result

Uriel Feige, Oleg Verbitsky

COMBINATORICA•Oct 1, 2002•35 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-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

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

Young Kun Ko

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

Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

Uma Girish, Mittal, Kunal, Ran Raz +1 more

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For $\textbf{every}$ 3-player game $\mathcal G$ over $\textit{binary questions}$ and $\textit{arbitrary answer lengths}$, with value less than 1, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Our proof technique is new and requires many new ideas. For example, we make use of the Level-$k$ inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.

arXiv:2204.00858•Apr 2, 2022•0 citations
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 ...
We prove that for every 3-player (3-prover) game G\mathcal GG with value less than one, whose query distribution has the support S={(1,0,0),(0,1,0),(0,0,1)}\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}S={(1,0,0),(0,1,0),(0,0,1)} of hamming weight one vectors, the value of the nnn-fold parallel repetition G⊗n\mathcal G^{\otimes n}G⊗n decays polynomially fast to zero; that is, there is a constant c=c(G)>0c = c(\mathcal G)>0c=c(G)>0 such that the value of the game G⊗n\mathcal G^{\otimes n}G⊗n is at most n−cn^{-c}n−c. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every\textbf{every}every 3-player game G\mathcal GG over binary questions\textit{binary questions}binary questions and arbitrary answer lengths\textit{arbitrary answer lengths}arbitrary answer lengths, with value less than 1, there is a constant c=c(G)>0c = c(\mathcal G)>0c=c(G)>0 such that the value of the game G⊗n\mathcal G^{\otimes n}G⊗n is at most n−cn^{-c}n−c. Our proof technique is new and requires many new ideas. For example, we make use of the Level-kkk inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.