A strong parallel repetition theorem for projection games on expanders

Ran Raz, Ricky Rosen

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

8 Scopus citations

Abstract

The parallel repetition theorem states that for any {\em Two Prover Game} with value at most 1-epsilon for epsilon.

Original languageEnglish (US)
Title of host publicationProceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012
Pages247-257
Number of pages11
DOIs
StatePublished - Sep 26 2012
Externally publishedYes
EventIEEE Computer Society Technical Committee on Mathematical Foundations of Computing - Porto, Portugal
Duration: Jun 26 2012Jun 29 2012

Publication series

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

Other

OtherIEEE Computer Society Technical Committee on Mathematical Foundations of Computing
CountryPortugal
CityPorto
Period6/26/126/29/12

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Keywords

  • complexity
  • parallel repetition

Fingerprint Dive into the research topics of 'A strong parallel repetition theorem for projection games on expanders'. Together they form a unique fingerprint.

  • Cite this

    Raz, R., & Rosen, R. (2012). A strong parallel repetition theorem for projection games on expanders. In Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012 (pp. 247-257). [6243401] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2012.11