O livro de Arora e Barak contém em notas de capítulo sobre PCP
Observamos que a estratégia geral de Dinur lembra um pouco a construção em zigue-zague de gráficos expansores e o algoritmo determinístico de espaço de log determinante de Reingold para conectividade não direcionada descrito no Capítulo 20, o que sugere que mais conexões estão sendo feitas entre essas diferentes áreas de pesquisa. (página 494)
O que exatamente significa essa reminiscência? Existe uma propriedade / lema comum que possa ser "fatorado" nessas duas provas?
cc.complexity-theory
pcp
sdcvvc
fonte
fonte
Respostas:
A resposta precisa à sua pergunta é dada por Oded Goldreich em seu artigo "Bravamente, Moderadamente: Um Tema Comum em Quatro Trabalhos Recentes".
Aqui está o link: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf
fonte