Le livre d'Arora et Barak contient des notes de chapitre sur PCP
Nous notons que la stratégie générale de Dinur rappelle quelque peu la construction en zig-zag des graphiques d'extension et l'algorithme déterministe de l'espace de journalisation de Reingold pour la connectivité non dirigée décrit au chapitre 20, ce qui suggère que plus de connexions attendent d'être établies entre ces différents domaines de recherche. (p. 494)
Qu'entend-on précisément par cette réminiscence? Existe-t-il une propriété / un lemme communs qui peuvent être «factorisés» de ces deux preuves?
cc.complexity-theory
pcp
sdcvvc
la source
la source
Réponses:
La réponse précise à votre question est donnée par Oded Goldreich dans son article "Courageusement, modérément: un thème commun dans quatre œuvres récentes".
Voici le lien: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf
la source