Koneksi antara PCP dan L = SL

9

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?

sdcvvc
sumber
4
Bagaimana hal-hal terjadi, Irit terinspirasi oleh bukti Omer ketika dia menemukan bukti PCP.
Dana Moshkovitz

Jawaban: