Borel-Cantelli Lemma dan Derandomisasi

11

Saya sedang membaca makalah berjudul Random Oracles with (out) Programmability . Paragraf terakhir dari bagian 2.3 berbunyi:

[Menggunakan pendekatan baru kami] tidak perlu menerapkan teknik derandomisasi asimtotik (dan seragam) klasik yang terkenal berdasarkan lemma Borel-Cantelli . Sejauh pengetahuan kami, pendekatan ini adalah novel untuk makalah ini.

Saya melihat entri Wikipedia untuk Borel – Cantelli lemma , dan hampir memahami gagasan itu. Namun, saya masih belum bisa mengetahui bagaimana hal itu berkaitan dengan derandomisasi. Selain itu, saya tidak mengerti arti "asimptotik" dan "seragam" dalam paragraf yang disebutkan di atas.

PS: Googling untuk Borel-Cantelli dan derandomisasi akan menunjukkan beberapa hasil yang menarik, tetapi saya tidak memiliki latar belakang yang cukup untuk memahaminya dengan baik.

cc.complexity-theory derandomization pr.probability measure-theory MS Dousti
sumber
2
Komitmen kecil: Penggunaan lemma Borel-Cantelli dalam teori kompleksitas tampaknya terkait dengan teori ukuran sumber daya terbatas yang diperkenalkan oleh Lutz , dan beberapa tindak lanjut di sini , di sini dan di sini . Saya juga tertarik dengan pertanyaan ini, semoga kami memiliki jawaban yang bagus!
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Terima kasih. Saya juga melihat karya-karya Lutz, tetapi mereka terlalu rumit untuk saya :( Saya harap seseorang menggambarkannya dalam "istilah awam";)
MS Dousti
t

Jawaban:

3

Saya tidak berpikir itu berarti derandomisasi dalam pengertian tradisional. Coba lihat penerapan lemma BC dalam makalah ini untuk contoh tentang apa yang mereka bicarakan: http://www.cs.bu.edu/~reyzin/hash.html .

Mereka mengatakan "asimptotik" karena sebagian besar pemisahan BB berlaku untuk konsep seperti fungsi satu arah, yang didefinisikan secara asimptotik. Hasilnya malah merupakan ikatan "konkret" yang berlaku untuk semua nilai parameter keamanan, bukan hanya nilai yang cukup besar.

David Cash
sumber