Skip to Main Content

Bulletin of the American Mathematical Society

The Bulletin publishes expository articles on contemporary mathematical research, written in a way that gives insight to mathematicians who may not be experts in the particular topic. The Bulletin also publishes reviews of selected books in mathematics and short articles in the Mathematical Perspectives section, both by invitation only.

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

The 2020 MCQ for Bulletin of the American Mathematical Society is 0.84.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


On Khot’s unique games conjecture
HTML articles powered by AMS MathViewer

by Luca Trevisan PDF
Bull. Amer. Math. Soc. 49 (2012), 91-111 Request permission


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.

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:
  • 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.
  • © Copyright 2011 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Bull. Amer. Math. Soc. 49 (2012), 91-111
  • MSC (2010): Primary 68Q17
  • DOI:
  • MathSciNet review: 2869009