¿Cuáles son buenas referencias para comprender la prueba del teorema de PCP?

Estoy familiarizado con muchos resultados que usan el teorema de PCP (principalmente en algoritmos de aproximación), pero nunca he encontrado una explicación clara del teorema de PCP (es decir, que ).$\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$

¿Cuáles son buenos papeles / libros para leer para eso?

Tanto el libro de texto de la complejidad de Goldreich y Arora y de Barak libro de texto de la complejidad tienen capítulos dedicados a explicar la prueba del teorema PCP (con fotos!).

Además, vale la pena leer el artículo de Dinur , si aún no ha tratado de abordarlo. Es al menos más accesible (en mi opinión) que la prueba original, y puede obtener una buena intuición de cómo funciona la prueba al hojear solo las primeras 12 páginas (y profundizar en las pruebas técnicas contenidas en la última parte del documento más adelante). , si tu prefieres).

En 2008, Irit Dinur y yo impartimos un curso sobre PCP en Weizmann, que incluía tanto las pruebas algebraicas como las pruebas combinatorias. Las notas de clase escritas a mano están disponibles para la mayoría de las clases: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

Este semestre estoy enseñando un curso de PCP en el MIT que contiene el material del curso anterior, un tratamiento más completo de la repetición paralela y la conjetura de los juegos únicos, así como resultados recientes (de 2008-2009), como composición de bajo error y óptima de programación semidefinida para problemas de satisfacción de restricciones asumiendo la conjetura de juegos únicos. También dedico tiempo a enseñar códigos de corrección de errores, expansores, teoría de la información y análisis de Fourier.

Este es el sitio web del curso: http://stellar.mit.edu/S/course/6/fa10/6.895/

Las notas están disponibles aquí: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

El artículo de Dinur (vinculado en la respuesta de Daniel Apon) está bien escrito y vale la pena leerlo. También se publicó una discusión extensa sobre este documento y la prueba, que es útil al leer el documento en sí: Jaikumar Radhakrishnan y Madhu Sudan, Sobre la prueba de Dinur del teorema de PCP , Bull. Amer Matemáticas. Soc. 44 (2007), 19-61 ( preimpresión ).

Las notas de clase del curso Guruswami & O'Donnell (UW, 2005) me parecieron muy útiles.

Para una vista de MUY alto nivel, me gustó mucho la publicación de blog de Tim Gower de hace unos días:

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

Realmente me ayudó a "obtener" la conexión con los códigos de corrección de errores y con la imposibilidad de acercarse.

Hubo un buen tutorial sobre el teorema de PCP y sus aplicaciones hace un año. Sus apuntes de clase deberían ser útiles: Límites de algoritmos de aproximación: PCP y juegos únicos (DIMACS Tutorial Lecture Notes)

Para la prueba original (y larga) del teorema de PCP, recomiendo las notas de Sudán como recapitulación y las notas de clase de Feige que explican la prueba en detalle.

Además, vea la publicación de Fortnow para otros materiales y discusiones útiles.

Sugeriría revisar las notas de clase de Eli-Ben Sasson . Además, las notas de clase de Prahladh Harsha contienen una exposición de ambas pruebas del teorema de PCP. El enlace al curso de Prahladh se puede encontrar en su página web TIFR (U Chicago Fall 2007). Las notas del curso de Venkat Guruswami y Ryan O'Donnell (como lo sugirió Hung Q. Ngo) también son muy buenas.

Hay 2 fuentes que me parecen particularmente buenas. Uno, como alguien sugirió anteriormente, son las notas de clase de Venkat y Ryan.

La otra fuente útil son estas notas de clase de Luca Trevisan.

Actualmente, Prasad Raghvendra ofrece este curso en Georgia Tech. Lamentablemente, la página aún no está abierta.

Esto me lleva a otra fuente de Subhash Khot. Búscalo en Google. Deberías poder encontrarlos.

(Personalmente, tampoco he buscado las notas de Khot, pero recordé que él también enseñó este curso una vez en GaTech)

Mi recomendación:

• para los informáticos novatos:

1- Pruebas y códigos probabilísticamente comprobables por Irit Dinur

2- Pruebas probabilísticamente comprobables por Madhu Sudán

3- Capítulo 9 del libro de Goldreich: complejidad computacional, una perspectiva conceptual

• para informáticos profesionales:

1- El teorema de PCP por Gap Amplification por Irit Dinur

2- Sobre la prueba de Dinur del teorema del PCP por jaikumar Radhakrishnan y Madhu Sudan

3- Capítulo 22 del libro de Arora y Barak: COMPLEJIDAD COMPUTACIONAL Un enfoque moderno

4- PCP robustos de proximidad y PCP más cortos de Prahladh Harsha (que cubre la primera prueba del teatro de PCP)

Para la prueba "clásica" (es decir, anterior a Dinur) del teorema de PCP, encontré la tesis de Prahladh Harsha como el mejor recurso.