Parallel repetition of two prover games

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

The parallel repetition theorem states that for any two-prover game with value smaller than 1, parallel repetition reduces the value of the game in an exponential rate. We give a short introduction to the problem of parallel repetition of two-prover games and some of its applications in theoretical computer science, mathematics and physics. We will concentrate mainly on recent results.

Original languageEnglish (US)
Title of host publicationProceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Pages3-6
Number of pages4
DOIs
StatePublished - 2010
Externally publishedYes
Event25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States
Duration: Jun 9 2010Jun 11 2010

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other25th Annual IEEE Conference on Computational Complexity, CCC 2010
Country/TerritoryUnited States
CityCambridge, MA
Period6/9/106/11/10

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Parallel repetition of two prover games'. Together they form a unique fingerprint.

Cite this