### 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 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 | |

State | Published - Nov 6 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 | United States |

City | Berkeley, CA |

Period | 8/21/09 → 8/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

*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