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

16 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 - 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
Country/TerritoryUnited 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