¿Qué evidencia tenemos a favor (y en contra) de la conjetura de juegos únicos?

Subhash Khot 's juegos únicos conjetura es una de las áreas de investigación activos en teoría de la complejidad.

¿Qué evidencia tenemos de ello? ¿Qué evidencia tenemos en contra?

cc.complexity-theory unique-games-conjecture Kaveh
fuente

¿Podría proporcionar algunas referencias, enlaces y qué evidencia tiene a favor o en contra? De lo contrario, haga que esta pregunta de tipo de lista grande sea un wiki de la comunidad.

András Salamon

Estoy de acuerdo en que debe ser wiki comunitario.

Moritz

como está redactado, definitivamente debería ser CW.

Suresh Venkat

Gracias a Daniel por el enlace a la buena encuesta de Khot. (Una publicación relacionada relativamente antigua en el blog Computational Complexity: blog.computationalcomplexity.org/2010/03/… )

Kaveh

Respuestas:

Khot dio una charla de encuesta UGC en CCC 2010. La reseña está aquí . El segmento final (parte inferior de la página 30) tiene sus opiniones sobre esta cuestión.

Daniel Apon
fuente

Otra encuesta interesante sobre UGC por Khot citada en [1] que está más orientada a las matemáticas:

S. Khot, Inaproximidad de problemas NP completos, Análisis discreto de Fourier y Geometría , ICM 2010.

[1] S. Khot, sobre la conjetura de juegos únicos , CCC 2010.

Kaveh
fuente