Quelles sont les bonnes références pour comprendre la preuve du théorème PCP?

Je connais pas mal de résultats qui utilisent le théorème PCP (principalement dans l'approximation d'algorithmes), mais je n'ai jamais trouvé d'explication claire du théorème PCP (c'est-à-dire que ).$\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$

Quels sont les bons papiers / livres à lire pour cela?

Les deux le manuel de la complexité de Goldreich et le manuel de la complexité de Arora et Barak ont des chapitres consacrés à expliquer la preuve du théorème PCP (avec des images!).

En outre, le papier de Dinur est intéressant à lire, si vous ne l'avez pas encore essayé. C'est au moins plus accessible (à mon avis) que la preuve originale, et vous pouvez obtenir une bonne intuition sur le fonctionnement de la preuve en parcourant seulement les 12 premières pages (et approfondissez ensuite les preuves techniques contenues dans le dernier morceau de papier , si tu préfères).

En 2008, Irit Dinur et moi avons donné à Weizmann un cours sur la PCP, comprenant à la fois les preuves algébriques et combinatoires. Des notes de cours manuscrites sont disponibles pour la plupart des cours: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

Ce semestre, j'enseigne un cours PCP au MIT qui contient le matériel de l'ancien cours, un traitement plus complet de la répétition parallèle et la conjecture unique des jeux, ainsi que des résultats récents (2008-2009), comme une composition d'erreur faible et une optimalité. de la programmation semi-finie pour les problèmes de satisfaction de contraintes en supposant la conjecture de jeux unique. Je consacre également du temps à l’enseignement des codes correcteurs d’erreur, des expandeurs, de la théorie de l’information et de l’analyse de Fourier.

Ceci est le site web du cours: http://stellar.mit.edu/S/course/6/fa10/6.895/

Les notes sont disponibles ici: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

L'article de Dinur (lié dans la réponse de Daniel Apon) est bien écrit et mérite d'être lu. Une discussion approfondie a également été publiée sur ce document et la preuve, ce qui est utile pour la lecture du document lui-même: Jaikumar Radhakrishnan et Madhu Sudan, La preuve du théorème du PCP par On Dinur , Bull. Amer. Math. Soc. 44 (2007), 19-61 ( préimpression ).

J'ai trouvé les notes de cours du cours Guruswami & O'Donnell (UW, 2005) très utiles.

Pour une vue de très haut niveau, j'ai vraiment aimé le post de blog de Tim Gower d'il y a quelques jours:

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

Vraiment m'a aidé à "obtenir" la connexion aux codes de correction d'erreur et à l'inapproximabilité.

Il y a un an, il y avait un bon tutoriel sur le théorème et les applications du PCP. Leurs notes de cours devraient être utiles: Limites des algorithmes d'approximation: PCP et jeux uniques (Notes de cours du didacticiel DIMACS)

Pour la preuve (longue et longue) du théorème du PCP, je recommande les notes du Soudan comme récapitulation et les notes de la conférence de Feige qui expliquent la preuve en détail.

Voir également le message de Fortnow pour d’autres documents et des discussions utiles.

Je suggérerais de parcourir les notes de cours d' Eli-Ben Sasson . De plus, les notes de cours de Prahladh Harsha contiennent et exposent les deux preuves du théorème de PCP. Le lien vers le cours de Prahladh est disponible sur sa page Web TIFR (U Chicago Fall 2007). Les notes de cours de Venkat Guruswami et Ryan O'Donnell (comme suggéré par Hung Q. Ngo) sont également très bonnes.

Il y a 2 sources qui me semblent particulièrement bonnes. L'une, comme quelqu'un de suggéré ci-dessus l'a suggéré, est les notes de conférence de Venkat et Ryan.

Les notes de cours de Luca Trevisan constituent l’ autre source utile .

Actuellement, ce cours est offert à Georgia Tech par Prasad Raghvendra. Malheureusement, la page n'est pas encore ouverte.

Cela m'amène à une autre source de Subhash Khot. Recherchez-le sur Google. Vous devriez pouvoir les trouver.

(Personnellement, je n'ai pas non plus consulté les notes de Khot, mais je viens juste de me rappeler qu'il avait également enseigné ce cours à GaTech)

Ma recommandation:

• pour les informaticiens débutants:

1- Preuves et codes vérifiables de manière probabiliste par Irit Dinur

2- Preuves vérifiables de manière probabiliste par Madhu Sudan

3- Chapitre 9 du livre de Goldreich: Complexité informatique, perspective conceptuelle

• pour les informaticiens professionnels:

1- Le théorème du PCP par Gap Amplification par Irit Dinur

2- Sur la preuve de Dinur du théorème du PCP par jaikumar Radhakrishnan et Madhu Sudan

3- Chapitre 22 du livre Arora et Barak: COMPLEXITÉ INFORMATIQUE Une approche moderne

4- Des PCP robustes de proximité et des PCP plus courts de Prahladh Harsha (qui couvre la première preuve du théorème du PCP)

Pour la preuve "classique" (c'est-à-dire, pré-Dinur) du théorème du PCP, j'ai trouvé la thèse de Prahladh Harsha la meilleure ressource.