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

2002/05/19 by Subhash Khot · 855 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Optimization and Search Problems #Gas meter prover #Conjecture #Mathematics #Constant (computer programming) #Repeated game #Value (mathematics) #Combinatorial game theory #Discrete mathematics #Computer science #Game theory #Mathematical economics #Programming language #Mathematical proof #Statistics #Geometry

paper · doi:10.1145/509907.510017

openalex publication_date 2002/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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 the following conjecture regarding the power of unique 2-prover games, which we call the Unique Games Conjecture:(MATH) The Unique Games Conjecture: For arbitrarily small constants ζ, δ > 0, there exists a constant k = k(ζ,δ) such that it is NP-hard to determine whether a unique 2-prover game with answers from a domain of size k has value at least 1-ζ or at most δ. \medskip.(MATH) We show that a positive resolution of this conjecture would imply the following hardness results:

Citations

• Probabilistic checking of proofs
• The importance of being biased
• Clique is hard to approximate within n1−ε
• A threshold of ln n for approximating set cover
• Proof verification and the hardness of approximation problems

Cited by

• Exact and Approximate Algorithms for Polytree Learning
• Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion
• A new point of NP-hardness for unique games
• Subexponential Algorithms for Unique Games and Related Problems
• Optimal algorithms and inapproximability results for every CSP?
• Graph expansion and the unique games conjecture
• On the Unique Games Conjecture (Invited Survey)
• Some topics in analysis of boolean functions
• Two Query PCP with Sub-Constant Error
• From average case complexity to improper learning complexity
• Vertex cover might be hard to approximate to within2−ε
• On the hardness of approximating vertex cover
• Krivine diffusions attain the Goemans--Williamson approximation ratio
• On the Usefulness of Predicates
• Streaming Hardness of Unique Games
• A modelling and computational study of the frustration index in signed networks
• Grothendieck‐Type Inequalities in Combinatorial Optimization
• The Grothendieck Constant is Strictly Smaller than Krivine's Bound
• Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
• Constrained Correlation Clustering: Towards Optimality
• On the Approximability of Boolean Max-k-CSP
• Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
• Max Cut
• Unique games conjecture [wikipedia]