Apa referensi yang baik untuk memahami bukti teorema PCP?

Saya akrab dengan banyak hasil yang menggunakan teorema PCP (terutama dalam algoritma perkiraan), tetapi saya tidak pernah menemukan penjelasan yang jelas tentang teorema PCP (yaitu, bahwa ).$\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$

Apa makalah / buku yang bagus untuk dibaca?

Baik buku teks kompleksitas Goldreich dan buku teks kompleksitas Arora dan Barak memiliki bab-bab yang ditujukan untuk menjelaskan bukti teorema PCP (dengan gambar!).

Juga, makalah Dinur bermanfaat untuk dibaca, jika Anda belum mencoba mengatasinya. Paling tidak lebih mudah didekati (menurut saya) daripada bukti asli, dan Anda bisa mendapatkan intuisi yang baik untuk bagaimana bukti bekerja dengan membaca sekilas hanya 12 halaman pertama (dan mempelajari bukti-bukti teknis yang terkandung dalam potongan kertas terakhir nanti) , jika kamu memilih).

Pada tahun 2008 Irit Dinur dan saya mengajar kursus tentang PCP di Weizmann, termasuk bukti aljabar dan kombinatorial. Catatan kuliah tulisan tangan tersedia untuk sebagian besar kelas: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

Semester ini saya mengajar kursus PCP di MIT yang berisi materi kursus lama, perawatan yang lebih komprehensif dari pengulangan paralel dan perkiraan game yang unik, serta hasil terbaru (dari 2008-2009), seperti komposisi kesalahan rendah dan optimalitas Pemrograman Semidefinite untuk masalah kepuasan kendala dengan asumsi Konjektur Game Unik. Saya juga mendedikasikan waktu untuk mengajar kode koreksi kesalahan, ekspander, teori informasi dan analisis Fourier.

Ini adalah situs web kursus: http://stellar.mit.edu/S/course/6/fa10/6.895/

Catatan tersedia di sini: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

Makalah Dinur (tertaut dalam jawaban oleh Daniel Apon) ditulis dengan baik dan layak dibaca. Diskusi panjang juga diterbitkan tentang makalah ini dan buktinya, yang berguna saat membaca makalah itu sendiri: Jaikumar Radhakrishnan dan Madhu Sudan, On Dinur tentang Bukti dari Teorema PCP , Bull. Amer. Matematika Soc. 44 (2007), 19-61 ( pracetak ).

Saya menemukan catatan kuliah dari kursus Guruswami & O'Donnell (UW, 2005) sangat berguna.

Untuk tampilan SANGAT tingkat tinggi saya sangat menyukai posting blog Tim Gower dari beberapa hari yang lalu:

http://gowers.wordpress.com/2010/08/30/icm2010-avila-dinur-plenary-lectures/

Benar-benar membantu saya "mendapatkan" koneksi ke kode koreksi kesalahan dan ke tidak terduga.

Ada tutorial yang bagus tentang teorema dan aplikasi PCP setahun yang lalu. Catatan kuliah mereka harus membantu: Batasan Algoritma Perkiraan: PCP dan Game Unik (Catatan Tutorial Tutorial DIMACS)

Untuk bukti asli (dan panjang) dari teorema PCP, saya merekomendasikan catatan Sudan sebagai rekap dan catatan kuliah Feige yang menjelaskan bukti secara rinci.

Juga, lihat posting Fortnow untuk bahan lain dan diskusi yang bermanfaat.

Saya sarankan membaca catatan kuliah Eli-Ben Sasson . Juga, catatan kuliah Prahladh Harsha berisi dan pemaparan kedua bukti Teorema PCP. Tautan ke kursus Prahladh dapat ditemukan di halaman web TIFR-nya (U Chicago Fall 2007). Catatan kursus Venkat Guruswami dan Ryan O'Donnell (seperti yang disarankan oleh Hung Q. Ngo) juga sangat bagus.

Ada 2 sumber yang tampaknya sangat baik bagi saya. Satu, seperti yang disarankan seseorang di atas adalah catatan kuliah Venkat dan Ryan.

Sumber bermanfaat lainnya adalah catatan kuliah ini oleh Luca Trevisan.

Saat ini, kursus ini ditawarkan di Georgia Tech oleh Prasad Raghvendra. Sayangnya halamannya belum bangun.

Ini membawa saya ke sumber lain oleh Subhash Khot. Cari di Google. Anda harus dapat menemukannya.

(Secara pribadi, saya juga belum melihat catatan Khot, tetapi hanya ingat bahwa dia pernah mengajar kursus ini di GaTech juga)

Rekomendasi saya:

• untuk ilmuwan komputer pemula:

1- Bukti dan Kode yang Kemungkinan Dapat Diperiksa oleh Irit Dinur

2- Bukti yang dapat diperiksa secara probabilistik oleh Madhu Sudan

3- Bab 9 dari buku Goldreich: Kompleksitas komputasi, Perspektif konseptual

• untuk ilmuwan komputer profesional:

1- Teorema PCP oleh Gap Amplification oleh Irit Dinur

2- Tentang Bukti Dinur tentang Teorema PCP oleh jaikumar Radhakrishnan dan Madhu Sudan

3- Bab 22 dari Arora dan buku barak: KOMPLEKSITAS KOMPUTASI Suatu Pendekatan Modern

4- PCP Proximity yang Dekat dan PCP yang Lebih Pendek oleh Prahladh Harsha (yang mencakup bukti pertama dari PCP therorem)

Untuk bukti "klasik" (yaitu, pra-Dinur) dari teorema PCP, saya menemukan tesis Prahladh Harsha sebagai sumber terbaik.