Title: On the power of unique 2-prover 1-round games
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 (we implicitly assume games to be one round games). The value of a 2-prover game is the maximum acceptance probability of the verifier over all the prover strategies. We make a conjecture regarding the power of unique 2-prover games, which we call the Unique Games Conjecture.
Publication Year: 2003
Publication Date: 2003-06-25
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 116
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot