Perbandingan ekstraktor dalam hal pertukaran antara waktu, keacakan dan ruang?

21

Apakah ada survei yang baik yang membandingkan berbagai ekstraktor, konsentrator dan superconcentrator dan menjabarkan metode terbaik dalam hal tradeoff antara keacakan, waktu dan ruang?

reference-request randomness derandomization Suresh Venkat
sumber
1
Hai Suresh, saya tidak berpikir extractors dan (super) -concentrator sebanding. Mungkin saya salah membaca pertanyaan, dan Anda bermaksud membandingkan algoritma konstruksi? Parameter untuk (super) -konsentrasi yang kami pedulikan adalah kedalaman dan ukurannya, bukan "keacakan, waktu, dan ruang". [Makalah Radhakrishnan dan Ta-shma] [1] memiliki tabel yang menunjukkan semua hasil yang ketat (termasuk referensi) untuk super-konsentrator. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo
Terimakasih atas klarifikasinya. Saya tidak pernah mengerti perbedaan di antara mereka.
Suresh Venkat

Jawaban:

12

Referensi default adalah survei Ronen Shaltiel . Ini mendahului hasil penting dari [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] dll saya percaya Anup Rao Ph.D . tesis adalah referensi baru yang bagus yang menggambarkan perkembangan ini.

arnab
sumber