Title :
Parallel Repetition of Two Prover Games (Invited Survey)
Author_Institution :
Fac. of Math., Weizmann Inst., Rehovot, Israel
Abstract :
The parallel repetition theorem states that for any two-prover game with value smaller than 1, parallel repetition reduces the value of the game in an exponential rate. We give a short introduction to the problem of parallel repetition of two-prover games and some of its applications in theoretical computer science, mathematics and physics. We will concentrate mainly on recent results.
Keywords :
game theory; parallel repetition theorem; prover games; theoretical computer science; Application software; Computational complexity; Computer science; Game theory; Mathematics; Physics; Probability distribution; Protocols; Radio access networks;
Conference_Titel :
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4244-7214-7
Electronic_ISBN :
1093-0159
