Parallel repetition of two prover games

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

1 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 - Aug 10 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
CountryUnited 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

    Raz, R. (2010). Parallel repetition of two prover games. In Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010 (pp. 3-6). [5497862] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2010.9