24

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • 1
    Could you provide some references, links, and what evidence you have for/against already? Otherwise please make this biglist type question a community wiki. – András Salamon Aug 17 '10 at 02:38
  • I agree that it should be community wiki. – Moritz Aug 17 '10 at 03:11
  • 1
    as phrased, it definitely should be CW. – Suresh Venkat Aug 17 '10 at 06:29
  • Thanks to Daniel for the link to Khot's nice survey. (A relatively older related post on Computational Complexity blog: http://blog.computationalcomplexity.org/2010/03/unique-games-redux.html) – Kaveh Aug 27 '10 at 13:11
  • 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. – Majid Zohrehbandian Jun 16 '22 at 12:59
  • Please don't use the "Post Your Answer" button to submit content which does not attempt to answer the question at the top of this page. If you want to post a new question, there is a separate "Ask" button for that; but probably review the [help] first, and in particular How to ask. – tripleee Jun 16 '22 at 13:00

2 Answers2

16

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.

Daniel Apon
  • 6,001
  • 1
  • 37
  • 53
10

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.

Kaveh
  • 21,577
  • 8
  • 82
  • 183