El libro de Arora y Barak contiene notas de capítulos sobre PCP
Observamos que la estrategia general de Dinur recuerda en cierta medida la construcción en zig-zag de los gráficos de expansión y el algoritmo determinista de espacio de registro de Reingold para la conectividad no dirigida que se describe en el Capítulo 20, lo que sugiere que hay más conexiones esperando entre estas diferentes áreas de investigación. (pág. 494)
¿Qué se entiende precisamente por esta reminiscencia? ¿Existe una propiedad / lema común que pueda "descartarse" de estas dos pruebas?
cc.complexity-theory
pcp
sdcvvc
fuente
fuente
Respuestas:
Oded Goldreich da la respuesta precisa a su pregunta en su artículo "Valientemente, moderadamente: un tema común en cuatro obras recientes".
Aquí está el enlace: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf
fuente