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 proceedingConference contribution

15 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 - ∈ 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).

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages352-365
Number of pages14
DOIs
StatePublished - Nov 6 2009
Externally publishedYes
Event12th 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 2009Aug 23 2009

Publication series

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

Other

Other12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
CountryUnited States
CityBerkeley, CA
Period8/21/098/23/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Strong parallel repetition theorem for free projection games'. Together they form a unique fingerprint.

  • 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