25
$\begingroup$

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?

$\endgroup$
6
  • 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$ Commented Aug 17, 2010 at 2:38
  • $\begingroup$ I agree that it should be community wiki. $\endgroup$
    – Moritz
    Commented Aug 17, 2010 at 3:11
  • 1
    $\begingroup$ as phrased, it definitely should be CW. $\endgroup$ Commented Aug 17, 2010 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
    Commented Aug 27, 2010 at 13:11
  • $\begingroup$ I proposed a better approximation algorithm for the vertex cover problem (a 1.999999-approximation algorithm by solving a well-known SDP model and a randomized procedure). It is not published, yet. But, I am sure that it is true (I am grateful if anyone identify any potential issues). I think my paper is an evidence against the Unique Games Conjecture. $\endgroup$ Commented Jun 16, 2022 at 12:59

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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