Paper Info
Title
Error Reduction by Parallel Repetition - A Negative Result
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
Year
DOI
Venue
2002
10.1007/s00493-002-0001-0
Philadelphia, PA
Keywords
DocType
Volume
two-prover one-round proof system,xed number,negative result,parallel repetition,answer length,error reduction,recent bound,fixed number,ran raz,parallel repetitions suffices,parallel repetitions su,leg,parallel algorithms,theorem proving,mathematics,computational complexity
Journal
22
Issue
ISSN
ISBN
4
0209-9683
0-8186-7386-9
Citations 
PageRank 
References 
26
2.60
18
Authors
2
Name
Order
Citations
PageRank
Uriel Feige15647560.87
Oleg Verbitsky219127.50