Bukti apa yang kami miliki untuk (dan menentang) Dugaan Game Unik?

23

Subhash Khot 's Unik Permainan Dugaan merupakan salah satu daerah penelitian aktif dalam teori kompleksitas.

Bukti apa yang kita miliki untuk itu? Bukti apa yang kita miliki menentangnya?

cc.complexity-theory unique-games-conjecture Kaveh
sumber
1
Bisakah Anda memberikan beberapa referensi, tautan, dan bukti apa yang sudah Anda miliki / lawan miliki? Kalau tidak, harap buat pertanyaan jenis daftar besar ini sebagai wiki komunitas.
András Salamon
Saya setuju bahwa itu harus wiki komunitas.
Moritz
1
seperti yang diungkapkan, itu pasti CW.
Suresh Venkat
Terima kasih kepada Daniel untuk tautan ke survei bagus Khot. (Posting terkait yang relatif lebih tua di blog Computational Complexity: blog.computationalcomplexity.org/2010/03/… )
Kaveh

Jawaban:

16

Khot memberi ceramah survei UGC di CCC 2010. Tulisannya ada di sini . Segmen terakhir (bagian bawah halaman 30) memiliki pendapatnya tentang pertanyaan ini.

Daniel Apon
sumber