Title :
Error reduction by parallel repetition-a negative result
Author :
Feige, Uriel ; Verbitsky, Oleg
Author_Institution :
Dept. of Appl. Math., Weizmann Inst. of Sci., Rehovot, Israel
Abstract :
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
Keywords :
computational complexity; parallel algorithms; theorem proving; error reduction; parallel repetition; two-prover one-round proof systems; Leg; Mathematics;
Conference_Titel :
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-7386-9
DOI :
10.1109/CCC.1996.507669
