Title :
Towards the parallel repetition conjecture
Author_Institution :
Dept. of Math. Logic, Moscow State Univ., Russia
fDate :
28 Jun- 1 Jul 1994
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315794
