Kompleksitas permintaan terbaik dari algoritma pembelajaran Goldreich-Levin / Kushilevitz-Mansour

Apa kompleksitas query yang paling dikenal dari algoritma pembelajaran Goldreich-Levin? Catatan kuliah dari blog Luca Trevisan , Lemma 3, menyatakannya sebagai . Apakah ini yang paling dikenal dalam hal ketergantungan pada n ? Saya akan sangat berterima kasih untuk referensi ke sumber yang dapat dicoba!$O(1/\epsilon^4 n \log n)$$n$

Pertanyaan terkait: apa kompleksitas query yang paling dikenal dari algoritma pembelajaran Kushilevitz-Mansour?

Pertanyaannya agak kurang spesifik dalam arti bahwa itu tidak menentukan probabilitas kesalahan yang diinginkan dari prosedur. Dengan asumsi satu berarti probabilitas kesalahan konstan, maka di atas memang yang terbaik yang saya tahu. Untuk diskusi terperinci lihat Bab 2.5.2.4 dalam buku saya "The Foundations of Cryptography - Volume 1" tersedia di http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

DI ATAS SALAH. LIHAT JAWABAN YANG BURUK DI BAWAH INI.

Prop 2.5.6 di bagian tersebut membuktikan ikatan yang jauh lebih baik: Algoritme berjalan dalam waktu yang diharapkan dikali waktu berjalan dari prosedur menebak (lihat peningkatan dari n 2 ke n dalam komentar tepat setelah bukti) dan benar wp p ( ϵ 2 ) . Oleh karena itu, ketepatan wp 2 / 3 diperoleh dalam waktu (faktor) ~ O ( n / ε 2 ) , yang optimal dalam arti (lihat Exer 30).$O(n \log^3(1/\epsilon))$$n^2$$n$$\Omega(\epsilon^2)$$2/3$${\tilde O}(n/\epsilon^2)$