Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory.

What evidence do we have for it? What evidence do we have against it?

  • 1
    $\begingroup$ Could you provide some references, links, and what evidence you have for/against already? Otherwise please make this biglist type question a community wiki. $\endgroup$ Aug 17 '10 at 2:38
  • $\begingroup$ I agree that it should be community wiki. $\endgroup$
    – Moritz
    Aug 17 '10 at 3:11
  • 1
    $\begingroup$ as phrased, it definitely should be CW. $\endgroup$ Aug 17 '10 at 6:29
  • $\begingroup$ Thanks to Daniel for the link to Khot's nice survey. (A relatively older related post on Computational Complexity blog: blog.computationalcomplexity.org/2010/03/…) $\endgroup$
    – Kaveh
    Aug 27 '10 at 13:11

Khot gave a UGC survey talk at CCC 2010. The write-up is here. The final segment (bottom of page 30) has his opinions on this question.


Another interesting survey about UGC by Khot cited in [1] which is more math oriented:

S. Khot, Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry, ICM 2010.

[1] S. Khot, On the Unique Games Conjecture, CCC 2010.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.