On Khot’s unique games conjecture
Author:
- 1 January 2012
- journal article
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 49 (1) , 91-111
Abstract
In 2002, Subhash Khot formulated the Unique Games Conjecture, a conjecture about the computational complexity of certain optimization problems.Keywords
This publication has 25 references indexed in Scilit:
- Noise stability of functions with low influences: Invariance and optimalityAnnals of Mathematics, 2010
- On the optimality of the random hyperplane rounding technique for MAX CUTRandom Structures & Algorithms, 2002
- Some optimal inapproximability resultsJournal of the ACM, 2001
- On Weighted vs Unweighted Versions of Combinatorial Optimization ProblemsInformation and Computation, 2001
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Combinatorial Properties and the Complexity of a Max-cut ApproximationEuropean Journal of Combinatorics, 1993
- Geometric bounds on the Ornstein-Uhlenbeck velocity processProbability Theory and Related Fields, 1985
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985