Strong parallel repetition theorem for free projection games

Boaz Barak; Anup Rao; Ran Raz; Ricky Rosen; Ronen Shaltiel

doi:10.1007/978-3-642-03685-9_27

Strong parallel repetition theorem for free projection games

Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

21 Scopus citations

Abstract

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 - ∈ ³) ^{Ω(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 - ∈ ²) ^Ω(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 - ∈ ²) ^{Ω(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).

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages	352-365
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-03685-9_27
State	Published - 2009
Externally published	Yes
Event	12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States Duration: Aug 21 2009 → Aug 23 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5687 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
Country/Territory	United States
City	Berkeley, CA
Period	8/21/09 → 8/23/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Barak, B., Rao, A., Raz, R., Rosen, R., & Shaltiel, R. (2009). Strong parallel repetition theorem for free projection games. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings (pp. 352-365). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS). https://doi.org/10.1007/978-3-642-03685-9_27

Barak, Boaz ; Rao, Anup ; Raz, Ran et al. / Strong parallel repetition theorem for free projection games. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. pp. 352-365 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ece396231d4f40c99e9ed7bec58eda5c,

title = "Strong parallel repetition theorem for free projection games",

abstract = "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).",

author = "Boaz Barak and Anup Rao and Ran Raz and Ricky Rosen and Ronen Shaltiel",

note = "Copyright: Copyright 2012 Elsevier B.V., All rights reserved.; 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 ; Conference date: 21-08-2009 Through 23-08-2009",

year = "2009",

doi = "10.1007/978-3-642-03685-9_27",

language = "English (US)",

isbn = "3642036848",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "352--365",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

Barak, B, Rao, A, Raz, R, Rosen, R & Shaltiel, R 2009, Strong parallel repetition theorem for free projection games. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5687 LNCS, pp. 352-365, 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009, Berkeley, CA, United States, 8/21/09. https://doi.org/10.1007/978-3-642-03685-9_27

Strong parallel repetition theorem for free projection games. / Barak, Boaz; Rao, Anup; Raz, Ran et al.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. p. 352-365 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

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 -

Barak B, Rao A, Raz R, Rosen R, Shaltiel R. Strong parallel repetition theorem for free projection games. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. p. 352-365. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03685-9_27

Strong parallel repetition theorem for free projection games

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this