Derandomisasi non-seragam yang lebih efisien?

16

Adleman, FOCS'78 menunjukkan bahwa setiap rangkaian acak untuk input dengan panjang dapat tidak dereragamkan. Namun, konstruksi secara efektif menduplikasi sirkuit asli O ( n ) kali, sehingga sirkuit derandomisasi lebih besar dari yang asli dengan faktor O ( n ) . Apakah ada konstruksi yang lebih efisien di luar sana yang mengalikan ukuran rangkaian dengan faktor yang lebih kecil?nO(n)O(n)

Piotr
sumber

Jawaban:

7

Saya tidak berpikir sesuatu yang lebih baik diketahui. Karena misalnya, jika dimungkinkan untuk derandomize sirkuit hanya dengan blowup sublinear, maka saya pikir itu juga mungkin untuk non-trivially (tetapi tidak seragam *) derandomize protokol komunikasi. Dan saya tidak percaya yang terakhir diketahui. Bukti Adleman memberikan blowup linier seperti yang Anda katakan, sehingga derandomisasi protokol komunikasi adalah sepele karena akan memberikan blowup linier dalam kompleksitas komunikasi.

*: Dengan "tidak seragam" dalam konteks protokol komunikasi, maksud saya algoritma untuk kedua pihak untuk menghitung bit berikutnya untuk dikirim ke yang lain tidak eksplisit. Saya ingat pernah membaca sebuah diskusi tentang ini di beberapa makalah, tetapi sepertinya saya tidak dapat menemukan referensi sekarang ...

arnab
sumber
Terima kasih, Arnab! Apakah ada referensi untuk argumen ini atau yang sejenis?
Piotr
4
Saya akhirnya menemukan kertas di mana saya melihat argumen ini! Ini adalah "derandomisasi algoritma lemah yang lemah" ( cs.haifa.ac.il/~ronen/online_papers/PID888174.pdf ) oleh Ronen Shaltiel. Makalah ini berbicara tentang derandomisasi seragam . Tetapi beberapa diskusi cukup relevan. Lihat Catatan Kaki 3 di halaman 2.
arnab