Error Reduction by Parallel Repetition—A Negative Result

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

Rotem Arnon-Friedman

Moshkovitz Aaronson, Dana Hadar

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.

James A. Williams, Douglas D. Hodson, Laurence D. Merkle

Jriel Feigt

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