Das Buch von Arora und Barak enthält in Kapitel Anmerkungen zu PCP
Wir stellen fest, dass Dinurs allgemeine Strategie etwas an die Zick-Zack-Konstruktion von Expander-Graphen und den in Kapitel 20 beschriebenen deterministischen Logspace-Algorithmus von Reingold für ungerichtete Konnektivität erinnert, was darauf hindeutet, dass weitere Verbindungen zwischen diesen verschiedenen Forschungsbereichen warten. (S. 494)
Was genau ist mit dieser Erinnerung gemeint? Gibt es eine gemeinsame Eigenschaft / ein gemeinsames Lemma, die aus diesen beiden Beweisen "herausgerechnet" werden kann?
cc.complexity-theory
pcp
sdcvvc
quelle
quelle
Antworten:
Die genaue Antwort auf Ihre Frage gibt Oded Goldreich in seinem Artikel "Tapfer, mäßig: Ein gemeinsames Thema in vier neueren Werken".
Hier ist der Link: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf
quelle