DocumentCode
1992304
Title
Towards the parallel repetition conjecture
Author
Verbitsky, Oleg
Author_Institution
Dept. of Math. Logic, Moscow State Univ., Russia
fYear
1994
fDate
28 Jun- 1 Jul 1994
Firstpage
304
Lastpage
307
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 Hales-Jewett´s theorem in Ramsey theory. This allows us to show that the error probability converges to 0 as n→∞
Keywords
automata theory; computational complexity; formal languages; game theory; theorem proving; Ramsey theory; error probability; incomplete information; parallel repetition conjecture; two-person cooperative game; two-prover one-round interactive protocol; Computational modeling; Error probability; Logic; Polynomials; Power system modeling; Protocols; Zinc;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location
Amsterdam
Print_ISBN
0-8186-5670-0
Type
conf
DOI
10.1109/SCT.1994.315794
Filename
315794
Link To Document