On the Unique Games Conjecture (Invited Survey)

2010/06/01 by Subhash Khot · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Advanced Graph Theory Research #Conjecture #Computer science #Mathematical economics #Theoretical computer science #Mathematics #Discrete mathematics

paper · doi:10.1109/ccc.2010.19

openalex publication_date 2010/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

This article surveys recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis, and geometry.

Citations

• Graph expansion and the unique games conjecture
• Probabilistic checking of proofs
• The importance of being biased
• Optimization, approximation, and complexity classes
• Clique is hard to approximate within n1−ε
• Interactive proofs and the hardness of approximating cliques
• Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
• Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
• Optimal algorithms and inapproximability results for every CSP?
• On the power of unique 2-prover 1-round games
• Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
• Vertex cover might be hard to approximate to within2−ε
• Proof verification and the hardness of approximation problems
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Differentiating maps into L¹ and the geometry of BV functions

Cited by

• Computational hardness assumption [wikipedia]
• Unique games conjecture [wikipedia]

Related

• On the Emergence of Ergodic Dynamics in Unique Games
• Unique Games and Games Based on Groups
• Sum-of-squares proofs and the quest toward optimal algorithms
• Reduction From Non-Unique Games To Boolean Unique Games
• Unique Games on the Hypercube