A strong parallel repetition theorem for projection games on expanders

Ran Raz; Ricky Rosen

doi:10.1109/CCC.2012.11

A strong parallel repetition theorem for projection games on expanders

Ran Raz, Ricky Rosen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

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

Original language	English (US)
Title of host publication	Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012
Pages	247-257
Number of pages	11
DOIs	https://doi.org/10.1109/CCC.2012.11
State	Published - 2012
Externally published	Yes
Event	IEEE Computer Society Technical Committee on Mathematical Foundations of Computing - Porto, Portugal Duration: Jun 26 2012 → Jun 29 2012

Publication series

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

Other

Other	IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
Country/Territory	Portugal
City	Porto
Period	6/26/12 → 6/29/12

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Keywords

complexity
parallel repetition

Access to Document

10.1109/CCC.2012.11

Cite this

@inproceedings{d04f011ed06047439094f0df7c83bf29,

title = "A strong parallel repetition theorem for projection games on expanders",

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

keywords = "complexity, parallel repetition",

author = "Ran Raz and Ricky Rosen",

year = "2012",

doi = "10.1109/CCC.2012.11",

language = "English (US)",

isbn = "9780769547084",

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

pages = "247--257",

booktitle = "Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012",

note = "IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; Conference date: 26-06-2012 Through 29-06-2012",

}

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., 6243401, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 247-257, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, Porto, Portugal, 6/26/12. https://doi.org/10.1109/CCC.2012.11

TY - GEN

T1 - A strong parallel repetition theorem for projection games on expanders

AU - Raz, Ran

AU - Rosen, Ricky

PY - 2012

Y1 - 2012

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

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

KW - complexity

KW - parallel repetition

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

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

U2 - 10.1109/CCC.2012.11

DO - 10.1109/CCC.2012.11

M3 - Conference contribution

AN - SCOPUS:84866510145

SN - 9780769547084

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 247

EP - 257

BT - Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012

T2 - IEEE Computer Society Technical Committee on Mathematical Foundations of Computing

Y2 - 26 June 2012 through 29 June 2012

ER -

A strong parallel repetition theorem for projection games on expanders

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this