On the power of unique 2-prover 1-round games

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

Abstract

A 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa. The value of a 2-prover game is the maximum acceptance probability of the verifier over all the prover strategies. Thus, the following conjecture regarding the power of unique 2-prover games, which is called the Unique Games Conjecture is made.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages767-775
Number of pages9
StatePublished - 2002
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

Other

OtherProceedings of the 34th Annual ACM Symposium on Theory of Computing
CountryCanada
CityMontreal, Que.
Period5/19/025/21/02

ASJC Scopus subject areas

  • Software

Cite this

Khot, S. (2002). On the power of unique 2-prover 1-round games. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 767-775)