Buku karya Arora dan Barak berisi dalam bab catatan tentang PCP
Kami mencatat bahwa strategi umum Dinur agak mengingatkan pada konstruksi zig-zag grafik expander dan algoritme logspace deterministik Reingold untuk konektivitas tidak terarah yang dijelaskan dalam Bab 20, yang menunjukkan bahwa lebih banyak koneksi sedang menunggu untuk dibuat antara berbagai bidang penelitian. (hal 494)
Apa tepatnya yang dimaksud dengan kenangan ini? Adakah properti / lemma umum yang bisa "difaktorkan" dari kedua bukti ini?
cc.complexity-theory
pcp
sdcvvc
sumber
sumber
Jawaban:
Jawaban tepat untuk pertanyaan Anda diberikan oleh Oded Goldreich dalam artikelnya "Bravely, Sedang: Tema Umum dalam Empat Karya Terbaru".
Berikut ini tautannya: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf
sumber