TY - GEN

T1 - Strong parallel repetition theorem for free projection games

AU - Barak, Boaz

AU - Rao, Anup

AU - Raz, Ran

AU - Rosen, Ricky

AU - Shaltiel, Ronen

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - The parallel repetition theorem states that for any two provers one round game with value at most 1- ∈ (for ∈ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∈ 3) Ω(n/log s) where s is the size of the answers set [Raz98],[Hol07]. For Projection Games the bound on the value of the game repeated n times in parallel was improved to (1 - ∈ 2) Ω(n) [Rao08] and was shown to be tight [Raz08]. In this paper we show that if the questions are taken according to a product distribution then the value of the repeated game is at most (1 - ∈ 2) Ω(n/log s) and if in addition the game is a Projection Game we obtain a strong parallel repetition theorem, i.e., a bound of (1-∈) Ω(n).

AB - The parallel repetition theorem states that for any two provers one round game with value at most 1- ∈ (for ∈ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∈ 3) Ω(n/log s) where s is the size of the answers set [Raz98],[Hol07]. For Projection Games the bound on the value of the game repeated n times in parallel was improved to (1 - ∈ 2) Ω(n) [Rao08] and was shown to be tight [Raz08]. In this paper we show that if the questions are taken according to a product distribution then the value of the repeated game is at most (1 - ∈ 2) Ω(n/log s) and if in addition the game is a Projection Game we obtain a strong parallel repetition theorem, i.e., a bound of (1-∈) Ω(n).

UR - http://www.scopus.com/inward/record.url?scp=70350600921&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350600921&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03685-9_27

DO - 10.1007/978-3-642-03685-9_27

M3 - Conference contribution

AN - SCOPUS:70350600921

SN - 3642036848

SN - 9783642036842

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 352

EP - 365

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009

Y2 - 21 August 2009 through 23 August 2009

ER -