Bulletin of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

On Khot's unique games conjecture

Author: Luca Trevisan
Journal: Bull. Amer. Math. Soc. 49 (2012), 91-111
MSC (2010): Primary 68Q17
Posted: November 7, 2011
Full-text PDF

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

1. N. Alon and V. D. Milman, 𝜆₁, isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88. MR 782626 (87b:05092), http://dx.doi.org/10.1016/0095-8956(85)90092-9
2. N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835 (88e:05077), http://dx.doi.org/10.1007/BF02579166
3. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, Proof verification and the hardness of approximation problems, J. ACM 45 (1998), no. 3, 501–555. MR 1639346 (99d:68077b), http://dx.doi.org/10.1145/278298.278306
4. Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70–122. MR 1614328 (99d:68077a), http://dx.doi.org/10.1145/273865.273901
5. Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. 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 R. Lee, and Assaf Naor, Euclidean distortion and the sparsest cut [extended abstract], STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 553–562. MR 2181659 (2006g:68284), http://dx.doi.org/10.1145/1060590.1060673
8. Sanjeev Arora, Satish Rao, and Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 222–231 (electronic). MR 2121604 (2005j:68081), http://dx.doi.org/10.1145/1007352.1007355
9. Mihir Bellare, Oded Goldreich, and Madhu Sudan, Free bits, PCPs, and nonapproximability—towards tight results, SIAM J. Comput. 27 (1998), no. 3, 804–915 (electronic). MR 1612644 (2000a:68034), http://dx.doi.org/10.1137/S0097539796302531
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, Z. Wahrsch. Verw. Gebiete 70 (1985), no. 1, 1–13. MR 795785 (87k:60103), http://dx.doi.org/10.1007/BF00532234
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, Inform. and Comput. 167 (2001), no. 1, 10–26. ISTCS’96 (Jerusalem). MR 1839896 (2003g:90058), http://dx.doi.org/10.1006/inco.2000.3011
16. Charles Delorme and Svatopluk Poljak, Combinatorial properties and the complexity of a max-cut approximation, European J. Combin. 14 (1993), no. 4, 313–333. MR 1226579 (94e:68139), http://dx.doi.org/10.1006/eujc.1993.1035
17. C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Programming 62 (1993), no. 3, Ser. A, 557–574. MR 1251892 (94k:90129), http://dx.doi.org/10.1007/BF01585184
18. Nikhil R. Devanur, Subhash A. Khot, Rishi Saket, and Nisheeth K. Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 537–546. MR 2277179 (2007h:68079), http://dx.doi.org/10.1145/1132516.1132594
19. Uriel Feige and Gideon Schechtman, On the optimality of the random hyperplane rounding technique for MAX CUT, Random Structures Algorithms 20 (2002), no. 3, 403–440. Probabilistic methods in combinatorial optimization. MR 1900615 (2003c:90086), http://dx.doi.org/10.1002/rsa.10036
20. Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228 (97g:90108), http://dx.doi.org/10.1145/227683.227684
21. Johan Håstad, Some optimal inapproximability results, J. ACM 48 (2001), no. 4, 798–859. MR 2144931 (2006c:68066), http://dx.doi.org/10.1145/502090.502098
22. Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 85–103. MR 0378476 (51 #14644)
23. Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 767–775. MR 2121525, http://dx.doi.org/10.1145/509907.510017
24. -, Inapproximability of -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 𝐿₁, SIAM J. Comput. 38 (2009), no. 6, 2487–2498. MR 2506299 (2010f:68238), http://dx.doi.org/10.1137/060660126
28. L. A. Levin, Universal enumeration problems, Problemy Peredači Informacii 9 (1973), no. 3, 115–116 (Russian). MR 0340042 (49 #4799)
29. Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), no. 1, 295–341. MR 2630040 (2012a:60091), http://dx.doi.org/10.4007/annals.2010.171.295
30. Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP? [extended abstract], STOC’08, ACM, New York, 2008, pp. 245–254. MR 2582901, http://dx.doi.org/10.1145/1374376.1374414
31. Ran Raz, A parallel repetition theorem, SIAM J. Comput. 27 (1998), no. 3, 763–803 (electronic). MR 1612640 (2000c:68057), http://dx.doi.org/10.1137/S0097539795280895
32. V. I. Rotar′, Limit theorems for polylinear forms, J. Multivariate Anal. 9 (1979), no. 4, 511–530. MR 556909 (81m:60039), http://dx.doi.org/10.1016/0047-259X(79)90055-1
33. Michael Sipser, Introduction to the theory of computation, Thomson, 2005, Second Editon.
34. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson, Gadgets, approximation, and linear programming, SIAM J. Comput. 29 (2000), no. 6, 2074–2097 (electronic). MR 1756405 (2001j:68046), http://dx.doi.org/10.1137/S0097539797328847
35. Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303 (2002h:68001)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|