Pengurangan kesalahan deterministik, canggih?

Asumsikan seseorang memiliki algoritma acak (BPP) $A$ menggunakan $r$ bit keacakan. Cara alami untuk memperbesar probabilitas keberhasilannya menjadi $1-\delta$ , untuk setiap $\delta>0$ , adalah

• Berjalan independen + suara terbanyak: jalankan $A$ secara independen $T=\Theta(\log(1/\delta)$ kali, dan mengambil suara mayoritas dari output. Ini membutuhkan $rT =\Theta(r\log(1/\delta))$ bit keacakan, dan meledakan waktu berjalan dengan faktor $T=\Theta(\log(1/\delta))$ .
• Berjalan bebas berpasangan + Chebyshev: jalankan $A$ "berpasangan-independen" $T=\Theta(1/\delta)$ kali, dan dibandingkan dengan ambang batas. Ini membutuhkan $rT =\Theta(r/\delta)$ bit keacakan, dan meledakkan waktu berjalan dengan a $T=\Theta(1/\delta)$ faktor.

Karp, Pippenger, dan Sipser [1] (tampaknya; saya tidak bisa mendapatkan kertas itu sendiri, ini adalah akun bekas) yang memberikan pendekatan alternatif berdasarkan ekspander reguler yang kuat: pada dasarnya, lihat $2^r$ node dari expander sebagai benih acak. Pilih simpul acak dari expander menggunakan bit acak $r$ , lalu

• lakukan jalan acak pendek dengan panjang $T=\Theta(\log(1/\delta))$ dari sana, dan jalankan $A$ pada biji $T$ sesuai dengan node di jalan, sebelum mengambil suara mayoritas. Ini membutuhkan $r+T = r+\Theta(\log(1/\delta))$ bit keacakan, dan meledakkan waktu berjalan dengan faktor $T=\Theta(\log(1/\delta))$ .

• jalankan $A$ pada semua tetangga dari node saat ini (atau, lebih umum, semua node dalam jarak $c$ dari node saat ini) sebelum mengambil suara terbanyak. Hal ini memerlukan $r$ bit keacakan, dan pukulan up waktu berjalan oleh $T=d$ faktor, di mana $d$ adalah derajat (atau $d^c$ untuk jarak- $c$ lingkungan. Menyiapkan parameter baik, ujung ini sampai biaya $T=\operatorname{poly}(1/\delta)$ sini.

Saya tertarik pada peluru terakhir, yang sesuai dengan pengurangan kesalahan deterministik . Apakah ada perbaikan setelah [1], mengurangi ketergantungan $T$ pada $\delta$ ? Apa pencapaian terbaik saat ini - $1/\delta^\gamma$ untuk mana $\gamma > 1$ ? $\gamma > 0$ ? (Untuk $\textsf{BPP}$ ? Untuk $\textsf{RP}$ ?)

Catatan: Saya juga (sangat) tertarik dengan $\textsf{RP}$ bukan $\textsf{BPP}$ . Seperti yang diperkenalkan pada [2], konstruksi yang relevan kemudian tidak lagi berekspansi, tetapi disperser (lihat misalnya, catatan kuliah ini oleh Ta-Shma, esp. Tabel 3). Saya tidak dapat menemukan batas yang sesuai untuk amplifikasi deterministik (bukan bit lebih acak daripada $r$ diizinkan ), namun, atau (lebih penting) apa konstruksi disperser eksplisit state-of-the-art untuk rentang parameter yang relevan adalah .

[1] Karp, R., Pippenger, N. dan Sipser, M., 1985. Tradeoff pengacakan waktu . Dalam Konferensi AMS tentang Kompleksitas Komputasi Probabilistik (Vol. 111).

[2] Cohen, A. dan Wigderson, A., 1989, Oktober. Disperser, amplifikasi deterministik, dan sumber acak yang lemah. Dalam Simposium Tahunan ke-30 tentang Yayasan Ilmu Komputer (hlm. 14-19). IEEE.

Bukankah catatan kuliah van Melkebeek sudah memberikan batas $O(1/\delta)$ ? Batasnya ada $\lambda$ paling banyak $O(\sqrt{\delta})$dan kita bisa mendapatkan$\lambda = O(1/\sqrt{d})$menggunakan konstruksi yang ada.

Dalam catatan kuliah Dwork juga, kondisi yang diperlukan adalah bahwa ekspansi menjadi $C/\delta$ untuk beberapa konstanta $C$ (melihat titik dalam jarak c pada dasarnya menggunakan powering untuk meningkatkan ekspansi). Yang lagi bisa didapatkan dengan derajat $O(1/\delta)$ .

$\Omega(1/\delta)$