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

<p>S. Khot, <a href="http://cs.nyu.edu/~khot/papers/icm-khot.pdf" rel="nofollow">Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry</a>, ICM 2010.</p>

<hr>

<p>[1] S. Khot, <a href="http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf" rel="nofollow">On the Unique Games Conjecture</a>, CCC 2010.</p>

CC BY-SA 2.5
2010-09-09T03:03:05.627Z
2010-09-09T03:03:05.627Z
Kaveh
<p>Khot gave a UGC survey talk at CCC 2010. The write-up is <a href="http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf" rel="noreferrer">here</a>. The final segment (bottom of page 30) has his opinions on this question.</p>

CC BY-SA 2.5
2010-08-17T02:47:50.323Z
2010-08-17T02:47:50.323Z
Daniel Apon
<p><a href="http://en.wikipedia.org/wiki/Subhash_Khot">Subhash Khot</a>'s <a href="http://en.wikipedia.org/wiki/Unique_games_conjecture">Unique Games Conjecture</a> is one of active research areas in complexity theory.</p>

<blockquote>
  <p>What evidence do we have for it? What evidence do we have against it?</p>
</blockquote>

CC BY-SA 4.0
2022-06-16T12:59:54.720Z
I proposed a better approximation algorithm for the vertex cover problem ([a 1.999999-approximation algorithm](https://vixra.org/abs/2107.0045) 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
CC BY-SA 4.0
2022-06-16T13:00:33.380Z
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.](/help/how-to-ask)
tripleee
CC BY-SA 2.5
2010-08-27T13:11:54.017Z
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
CC BY-SA 2.5
2010-08-17T02:38:17.053Z
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
CC BY-SA 2.5
2010-08-17T03:11:18.613Z
I agree that it should be community wiki.
Moritz
CC BY-SA 2.5
2010-08-17T06:29:10.083Z
as phrased, it definitely should be CW.
Suresh Venkat
<cc.complexity-theory><unique-games-conjecture>
What evidence do we have for (and against) Unique Games Conjecture?
Kaveh
# What evidence do we have for (and against) Unique Games Conjecture?

(Asked by: username_0 on 2010-08-17)

[Subhash Khot](http://en.wikipedia.org/wiki/Subhash_Khot)'s [Unique Games Conjecture](http://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, unique-games-conjecture
> **Comments:**
> **username_3**: Could you provide some references, links, and what evidence you have for/against already?  Otherwise please make this biglist type question a community wiki.  
> **username_4**: I agree that it should be community wiki.  
> **username_5**: as phrased, it definitely should be CW.  
> **username_0**: 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)  
> **username_1**: I proposed a better approximation algorithm for the vertex cover problem ([a 1.999999-approximation algorithm](https://vixra.org/abs/2107.0045) 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.  
> **username_2**: 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.](/help/how-to-ask)  

---

## 2 answers

### Answer by username_6 on 2010-08-17. Score: 16 | Accepted answer

Khot gave a UGC survey talk at CCC 2010. The write-up is [here](http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf). The final segment (bottom of page 30) has his opinions on this question.


---

### Answer by username_0 on 2010-09-09. Score: 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](http://cs.nyu.edu/~khot/papers/icm-khot.pdf), ICM 2010.

---

[1] S. Khot, [On the Unique Games Conjecture](http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf), CCC 2010.


---

