• DocumentCode
    2834170
  • Title

    On the Unique Games Conjecture (Invited Survey)

  • Author

    Khot, Subhash

  • Author_Institution
    Courant Inst. of Math. Sci., NYU, New York, NY, USA
  • fYear
    2010
  • fDate
    9-12 June 2010
  • Firstpage
    99
  • Lastpage
    121
  • Abstract
    This article surveys recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis, and geometry.
  • Keywords
    Fourier analysis; computational complexity; game theory; geometry; computational complexity; discrete Fourier analysis; geometry; unique games conjecture; Algorithm design and analysis; Approximation algorithms; Computational complexity; Computational geometry; Engineering profession; Hypercubes; NP-complete problem; Polynomials; Programming profession; User-generated content;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
  • Conference_Location
    Cambridge, MA
  • ISSN
    1093-0159
  • Print_ISBN
    978-1-4244-7214-7
  • Electronic_ISBN
    1093-0159
  • Type

    conf

  • DOI
    10.1109/CCC.2010.19
  • Filename
    5497893
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2834170