Skip to Main Content

Bulletin of the American Mathematical Society

Published by the American Mathematical Society, the Bulletin of the American Mathematical Society (BULL) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

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

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

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
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
  • 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: https://doi.org/10.1090/S0273-0979-2011-01361-1
  • MathSciNet review: 2869009