Parallel repetition of two prover games

Ran Raz

doi:10.1109/CCC.2010.9

Parallel repetition of two prover games

Ran Raz

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Pages	3-6
Number of pages	4
DOIs	https://doi.org/10.1109/CCC.2010.9
State	Published - 2010
Externally published	Yes
Event	25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States Duration: Jun 9 2010 → Jun 11 2010

Publication series

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

Other

Other	25th Annual IEEE Conference on Computational Complexity, CCC 2010
Country/Territory	United States
City	Cambridge, MA
Period	6/9/10 → 6/11/10

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2010.9

Cite this

@inproceedings{1d93f7a803354595bee058405669a959,

title = "Parallel repetition of two prover games",

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.",

author = "Ran Raz",

year = "2010",

doi = "10.1109/CCC.2010.9",

language = "English (US)",

isbn = "9780769540603",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "3--6",

booktitle = "Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010",

note = "25th Annual IEEE Conference on Computational Complexity, CCC 2010 ; Conference date: 09-06-2010 Through 11-06-2010",

}

TY - GEN

T1 - Parallel repetition of two prover games

AU - Raz, Ran

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955254155&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955254155&partnerID=8YFLogxK

U2 - 10.1109/CCC.2010.9

DO - 10.1109/CCC.2010.9

M3 - Conference contribution

AN - SCOPUS:77955254155

SN - 9780769540603

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 3

EP - 6

BT - Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010

T2 - 25th Annual IEEE Conference on Computational Complexity, CCC 2010

Y2 - 9 June 2010 through 11 June 2010

ER -

Parallel repetition of two prover games

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this