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

   
Mobile Device Pairing
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

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?)


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
Email: trevisan@stanford.edu

DOI: http://dx.doi.org/10.1090/S0273-0979-2011-01361-1
PII: S 0273-0979(2011)01361-1
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.