Was sind gute Referenzen zum Verständnis des Beweises des PCP-Theorems?

Ich kenne viele Ergebnisse, die das PCP-Theorem verwenden (hauptsächlich zur Approximation von Algorithmen), aber ich bin nie auf eine klare Erklärung des PCP-Theorems (dh, dass ).$\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$

Was sind dafür gute Papiere / Bücher?

Sowohl Goldreich Komplexität Lehrbuch und Arora und Baraks Komplexität Lehrbuch haben Kapitel gewidmet Erläuterung der Nachweis des PCP - Theorem (mit Bildern!).

Es lohnt sich auch, Dinurs Artikel zu lesen, wenn Sie noch nicht versucht haben, ihn in Angriff zu nehmen. Es ist zumindest (meiner Meinung nach) zugänglicher als der Original-Proof, und Sie können eine gute Vorstellung davon bekommen, wie der Proof funktioniert, indem Sie nur die ersten 12 Seiten überfliegen (und später in die technischen Proofs eintauchen, die im letzten Teil des Papiers enthalten sind , wenn Sie es vorziehen).

2008 unterrichteten Irit Dinur und ich bei Weizmann einen PCP-Kurs, der sowohl algebraische als auch kombinatorische Beweise enthielt. Handschriftliche Vorlesungsunterlagen sind für die meisten Klassen verfügbar: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

In diesem Semester unterrichte ich einen PCP-Kurs am MIT, der das Material des alten Kurses, eine umfassendere Behandlung paralleler Wiederholungen und die einzigartige Spielvermutung sowie aktuelle Ergebnisse (von 2008 bis 2009) wie eine fehlerarme Komposition und Optimalität enthält der semidefiniten Programmierung für Bedingungserfüllungsprobleme unter der Annahme der Unique Games Conjecture. Ich widme mich auch der Vermittlung von Fehlerkorrekturcodes, Expander, Informationstheorie und Fourier-Analyse.

Dies ist die Website des Kurses: http://stellar.mit.edu/S/course/6/fa10/6.895/

Hinweise finden Sie hier: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

Dinurs Artikel (in der Antwort von Daniel Apon verlinkt) ist gut geschrieben und lesenswert. Es wurde auch eine ausführliche Diskussion über dieses Papier und den Beweis veröffentlicht, der nützlich ist, wenn man das Papier selbst liest: Jaikumar Radhakrishnan und Madhu Sudan, On Dinurs Proof of the PCP Theorem , Bull. Amer. Mathematik. Soc. 44 (2007), 19-61 ( Vordruck ).

Ich fand die Vorlesungsunterlagen des Guruswami & O'Donnell-Kurses (UW, 2005) sehr nützlich.

Für eine SEHR gute Ansicht mochte ich Tim Gowers Blogpost von vor ein paar Tagen:

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

Hat mir wirklich geholfen, die Verbindung zu fehlerkorrigierenden Codes und zur Unangemessenheit "herzustellen".

Vor einem Jahr gab es ein nettes Tutorial zum PCP-Theorem und zu Anwendungen. Ihre Vorlesungsunterlagen sollten hilfreich sein: Grenzen von Approximationsalgorithmen: PCPs und einzigartige Spiele (DIMACS Tutorial Lecture Notes)

Für den ursprünglichen (und langen) Beweis des PCP-Theorems empfehle ich Sudans Notizen als Zusammenfassung und Feiges Vorlesungsnotizen, die den Beweis im Detail erläutern.

Weitere Materialien und nützliche Diskussionen finden Sie in Fortnows Post .

Ich würde vorschlagen, Eli-Ben Sassons Vorlesungsnotizen durchzugehen . Außerdem enthalten Prahladh Harshas Vorlesungsunterlagen beide Beweise des PCP-Theorems und legen sie dar. Den Link zu Prahladhs Kurs finden Sie auf seiner TIFR-Webseite (U Chicago Fall 2007). Die Kursnoten von Venkat Guruswami und Ryan O'Donnell (wie von Hung Q. Ngo vorgeschlagen) sind ebenfalls sehr gut.

Es gibt zwei Quellen, die mir besonders gut erscheinen. Eines ist, wie oben erwähnt, das Skript von Venkat und Ryan.

Die andere hilfreiche Quelle ist das Skript von Luca Trevisan.

Derzeit wird dieser Kurs an der Georgia Tech von Prasad Raghvendra angeboten. Leider ist die Seite noch nicht online.

Dies bringt mich zu einer anderen Quelle von Subhash Khot. Suche danach bei Google. Sie sollten in der Lage sein, diese zu finden.

(Persönlich habe ich auch Khots Notizen nicht nachgeschlagen, sondern nur daran gedacht, dass er diesen Kurs auch einmal bei GaTech unterrichtet hat.)

Meine Empfehlung:

• für Anfänger Informatiker:

1- Probabilistisch überprüfbare Beweise und Codes von Irit Dinur

2- Probabilistisch überprüfbare Beweise von Madhu Sudan

3- Kapitel 9 aus dem Goldreich-Buch: Computerkomplexität, Eine konzeptionelle Perspektive

• für professionelle Informatiker:

1- Der PCP-Satz von Gap Amplification von Irit Dinur

2- Zu Dinurs Beweis des PCP-Theorems von Jaikumar Radhakrishnan und Madhu Sudan

3- Kapitel 22 aus dem Buch von Arora und Barak: COMPUTATIONAL COMPLEXITY Ein moderner Ansatz

4- Robuste PCPs der Nähe und kürzere PCPs von Prahladh Harsha (das den ersten Beweis des PCP-Therorems umfasst)

Für den "klassischen" (dh vor Dinur) Beweis des PCP-Theorems fand ich Prahladh Harshas These die beste Ressource.