Quais são as boas referências para entender a prova do teorema do PCP?

Eu estou familiarizado com uma série de resultados que usam o teorema PCP (principalmente na aproximação de algoritmos), mas eu nunca me deparei com uma explicação clara do teorema PCP (ou seja, que ).$\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$

Quais são os bons papéis / livros para ler para isso?

Ambos livro complexidade do Goldreich e de Arora e Barak livro complexidade tem capítulos dedicados a explicar a prova do teorema PCP (com fotos!).

Também vale a pena ler o artigo de Dinur , se você ainda não tentou abordá-lo. É pelo menos mais acessível (na minha opinião) do que a prova original, e você pode ter uma boa intuição de como a prova funciona deslizando apenas as primeiras 12 páginas (e se aprofundar nas provas técnicas contidas posteriormente no último pedaço do artigo) , se você preferir).

Em 2008, Irit Dinur e eu ministramos um curso sobre PCP em Weizmann, incluindo as provas algébricas e combinatórias. Notas de aula escritas à mão estão disponíveis para a maioria das aulas: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

Neste semestre, estou ministrando um curso PCP no MIT que contém o material do curso antigo, tratamento mais abrangente da repetição paralela e a conjectura de jogos únicos, além de resultados recentes (de 2008 a 2009), como baixa composição de erros e otimização de Programação Semidefinida para problemas de satisfação de restrições assumindo a Conjectura de Jogos Exclusivos. Também dedico tempo ao ensino de códigos de correção de erros, expansores, teoria da informação e análise de Fourier.

Este é o site do curso: http://stellar.mit.edu/S/course/6/fa10/6.895/

As notas estão disponíveis aqui: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

O artigo de Dinur (linkado na resposta de Daniel Apon) está bem escrito e vale a pena ler. Também foi publicada uma discussão extensa sobre este artigo e a prova, que é útil ao ler o artigo em si: Jaikumar Radhakrishnan e Madhu Sudan, Sobre a Prova de Dinur do Teorema do PCP , Bull. Amer. Matemática. Soc. 44 (2007), 19-61 ( pré-impressão ).

Achei as anotações das aulas do curso Guruswami & O'Donnell (UW, 2005) muito úteis.

Para uma visualização de alto nível, gostei muito do post de Tim Gower de alguns dias atrás:

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

Realmente me ajudou a "obter" a conexão com os códigos de correção de erros e a falta de aproximação.

Houve um bom tutorial sobre o teorema do PCP e aplicações há um ano. Suas anotações de aula devem ser úteis: Limites de algoritmos de aproximação: PCPs e jogos exclusivos (Notas da palestra do tutorial DIMACS)

Para a prova original (e longa) do teorema do PCP, recomendo as anotações do Sudão como uma recapitulação e as anotações da aula de Feige, que explicam a prova em detalhes.

Veja também a publicação de Fortnow para outros materiais e discussões úteis.

Eu sugeriria examinar as notas da aula de Eli-Ben Sasson . Além disso, as notas de aula de Prahladh Harsha contêm e exposição de ambas as provas do Teorema do PCP. O link para o curso de Prahladh pode ser encontrado em sua página TIFR (U Chicago Fall 2007). As notas do curso de Venkat Guruswami e Ryan O'Donnell (como sugerido por Hung Q. Ngo) também são muito boas.

Existem 2 fontes que me parecem particularmente boas. Um, como alguém acima sugeriu, são as anotações de Venkat e Ryan.

A outra fonte útil são essas notas de aula de Luca Trevisan.

Atualmente, este curso está sendo oferecido na Georgia Tech por Prasad Raghvendra. Infelizmente a página ainda não está aberta.

Isso me leva a outra fonte de Subhash Khot. Pesquise no Google. Você deve conseguir encontrá-los.

(Pessoalmente, eu também não procurei as anotações de Khot, mas lembrei-me de que ele também ministrou este curso na GaTech)

Minha recomendação:

• para cientistas da computação novatos:

1- Provas e códigos verificáveis ​​probabilisticamente por Irit Dinur

2- Provas probabilisticamente verificáveis de Madhu Sudan

3- Capítulo 9 do livro de Goldreich: complexidade computacional, uma perspectiva conceitual

• Para cientistas profissionais da computação:

1- O Teorema do PCP por Gap Amplification por Irit Dinur

2- Sobre a prova de Dinur do teorema do PCP, por jaikumar Radhakrishnan e Madhu Sudan

3- Capítulo 22 do livro Arora e barak: COMPLEXIDADE COMPUTACIONAL Uma Abordagem Moderna

4- PCPs robustos de proximidade e PCPs mais curtos de Prahladh Harsha (que abrange a primeira prova do theremem de PCP)

Para a prova "clássica" (ou seja, pré-Dinur) do teorema do PCP, achei a tese de Prahladh Harsha o melhor recurso.