Paper Info
Title
Towards the parallel repetition conjecture
Abstract
We consider the behavior of the error probability of a two-prover one-round interactive protocol repeated n times in parallel. We point out the connection of this problem with the density form of the Hales-Jewett theorem in Ramsey theory. This allows us to show that the error probability converges to 0 as n → ∞.
Year
DOI
Venue
1994
10.1016/0304-3975(95)00165-4
Theoretical Computer Science - Special issue on complexity theory and the theory of algorithms as developed in the CIS
Keywords
DocType
Volume
parallel repetition conjecture,game theory,theorem proving,computational complexity,automata theory,ramsey theory,formal languages,error probability
Conference
157
Issue
ISSN
ISBN
2
0304-3975
0-8186-5670-0
Citations 
PageRank 
References 
14
3.57
7
Authors
1
Name
Order
Citations
PageRank
Oleg Verbitsky119127.50