Que evidência temos a favor (e contra) a conjectura de jogos exclusivos?

Subhash Khot 's únicos Jogos Conjectura é uma das áreas de pesquisa ativos na teoria da complexidade.

Que evidência temos para isso? Que evidência temos contra isso?

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

Você poderia fornecer algumas referências, links e quais evidências você já possui a favor / contra? Caso contrário, faça desta pergunta do tipo biglist um wiki da comunidade.

András Salamon

Concordo que deveria ser wiki da comunidade.

Moritz

como foi dito, definitivamente deveria ser CW.

Suresh Venkat

Obrigado a Daniel pelo link para a boa pesquisa de Khot. (Uma publicação relacionada relativamente mais antiga no blog da Computational Complexity: blog.computationalcomplexity.org/2010/03/… )

Kaveh

Respostas:

Khot fez uma palestra de pesquisa UGC na CCC 2010. A redação está aqui . O segmento final (parte inferior da página 30) tem suas opiniões sobre esta questão.

Daniel Apon
fonte

Outra pesquisa interessante sobre UGC por Khot citada em [1], que é mais orientada para a matemática:

S. Khot, Inaproximabilidade de Problemas NP-completos, Análise Discreta de Fourier e Geometria , ICM 2010.

[1] S. Khot, Sobre a conjetura de jogos exclusivos , CCC 2010.

Kaveh
fonte