Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



On Khot's unique games conjecture

Author: Luca Trevisan
Journal: Bull. Amer. Math. Soc. 49 (2012), 91-111
MSC (2010): Primary 68Q17
Published electronically: November 7, 2011
MathSciNet review: 2869009
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In 2002, Subhash Khot formulated the Unique Games Conjecture, a conjecture about the computational complexity of certain optimization problems.

The conjecture has inspired a remarkable body of work, which has clarified the computational complexity of several optimization problems and the effectiveness of ``semidefinite programming'' convex relaxations.

In this paper, which assumes no prior knowledge of computational complexity, we describe the context and statement of the conjecture, and we discuss in some detail one specific line of work motivated by it.

References [Enhancements On Off] (What's this?)

  • 1. N. Alon and V.D. Milman, $ \lambda _1$, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, Series B 38 (1985), no. 1, 73-88. MR 782626 (87b:05092)
  • 2. Noga Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83-96. MR 875835 (88e:05077)
  • 3. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, Journal of the ACM 45 (1998), no. 3, 501-555, Preliminary version in Proc. of FOCS '92. MR 1639346 (99d:68077b)
  • 4. S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP, Journal of the ACM 45 (1998), no. 1, 70-122, Preliminary version in Proc. of FOCS '92. MR 1614328 (99d:68077a)
  • 5. Sanjeev Arora and Boaz Barak, Computational complexity: A modern approach, Cambridge University Press, 2009. MR 2500087 (2010i:68001)
  • 6. Sanjeev Arora, Boaz Barak, and David Steurer, Subexponential algorithms for unique games and related problems, Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 2010.
  • 7. Sanjeev Arora, James Lee, and Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the 37th ACM Symposium on Theory of Computing, 2005, pp. 553-562. MR 2181659 (2006g:68284)
  • 8. Sanjeev Arora, Satish Rao, and Umesh Vazirani, Expander flows and a $ \sqrt {\log n}$-approximation to sparsest cut, Proceedings of the 36th ACM Symposium on Theory of Computing, 2004. MR 2121604 (2005j:68081)
  • 9. M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCP's and non-approximability - towards tight results, SIAM Journal on Computing 27 (1998), no. 3, 804-915, Preliminary version in Proc. of FOCS '95. MR 1612644 (2000a:68034)
  • 10. M Bellare, S. Goldwasser, C. Lund, and A. Russell, Efficient probabilistically checkable proofs and applications to approximation, Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, See also the errata sheet in Proc of STOC '94, pp. 294-304.
  • 11. Christer Borell, Geometric bounds on the Ornstein-Uhlenbeck velocity process, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 70 (1985), 1-13. MR 795785 (87k:60103)
  • 12. Moses Charikar, Konstantin Makarychev, and Yury Makarychev, Near-optimal algorithms for unique games, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 205-214.
  • 13. Jeff Cheeger, Bruce Kleiner, and Assaf Naor, A $ (\log n)^{\Omega (1)}$ integrality gap for the sparsest cut SDP, arxiv:0910.2024, 2009.
  • 14. S.A. Cook, The complexity of theorem proving procedures, Proceedings of the 3rd ACM Symposium on Theory of Computing, 1971, pp. 151-158.
  • 15. Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan, On weighted vs unweighted versions of combinatorial optimization problems, Information and Compututation 167 (2001), no. 1, 10-26. MR 1839896 (2003g:90058)
  • 16. Charles Delorme and Svatopluk Poljak, Combinatorial properties and the complexity of a max-cut approximation, European J. of Combinatorics 14 (1993), no. 4, 313-333. MR 1226579 (94e:68139)
  • 17. -, Laplacian eigenvalues and the maximum cut problem, Mathematical Programing 62 (1993), 557-574. MR 1251892 (94k:90129)
  • 18. Nikhil Devanur, Subhash Khot, Rishi Saket, and Nisheeth Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 537-546. MR 2277179 (2007h:68079)
  • 19. Uriel Feige and Gideon Schechtman, On the optimality of the random hyperplane rounding technique for MAX CUT, Random Structures and Algorithms 20 (2002), no. 3, 403-440. MR 1900615 (2003c:90086)
  • 20. Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42 (1995), no. 6, 1115-1145, Preliminary version in Proc. of STOC'94. MR 1412228 (97g:90108)
  • 21. Johan Håstad, Some optimal inapproximability results, Journal of the ACM 48 (2001), no. 4, 798-859. MR 2144931 (2006c:68066)
  • 22. R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.), Plenum Press, 1972, pp. 85-103. MR 0378476 (51:14644)
  • 23. Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the 34th ACM Symposium on Theory of Computing, 2002, pp. 767-775. MR 2121525
  • 24. -, Inapproximability of $ NP$-complete problems, discrete Fourier analysis, and geometry, Proceedings of the International Congress of Mathematicians, 2010.
  • 25. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs?, Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004, pp. 146-154.
  • 26. Subhash Khot and Nisheeth Vishnoi, The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into $ \ell _1$, Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 53-63.
  • 27. Robert Krauthgamer and Yuval Rabani, Improved lower bounds for embeddings into L1, SIAM Journal on Computing 38 (2009), no. 6, 2487-2498. MR 2506299 (2010f:68238)
  • 28. Leonid A. Levin, Universal search problems, Problemi Peredachi Informatsii 9 (1973), 265-266. MR 0340042 (49:4799)
  • 29. Elchanan Mossel, Ryan O'Donnell and, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: Invariance and optimality, Annals of Mathematics 171 (2010), no. 1, 295-341. MR 2630040
  • 30. Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the 40th ACM Symposium on Theory of Computing, 2008. MR 2582901
  • 31. Ran Raz, A parallel repetition theorem, SIAM Journal on Computing 27 (1998), no. 3, 763-803, Preliminary version in Proc. of STOC '95. MR 1612640 (2000c:68057)
  • 32. V. I. Rotar, Limit theorems for polylinear forms, J of Multivariate Analysis 9 (1979), no. 4, 511-530. MR 556909 (81m:60039)
  • 33. Michael Sipser, Introduction to the theory of computation, Thomson, 2005, Second Editon.
  • 34. L. Trevisan, G.B. Sorkin, M. Sudan, and D.P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing 29 (2000), no. 6, 2074-2097. MR 1756405 (2001j:68046)
  • 35. Vijay Vazirani, Approximation algorithms, Springer, 2001. MR 1851303 (2002h:68001)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 68Q17

Retrieve articles in all journals with MSC (2010): 68Q17

Additional Information

Luca Trevisan
Affiliation: Computer Science Department, Stanford University, 353 Serra Mall Stanford, California 94305-9025

Received by editor(s): July 18, 2011
Received by editor(s) in revised form: July 25, 2011
Published electronically: November 7, 2011
Additional Notes: This material is based upon work supported by the National Science Foundation under Grant No. CCF-1017403.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society