Najlepsza złożoność zapytań algorytmu uczenia się Goldreich-Levin / Kushilevitz-Mansour

Jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Goldreich-Levin? Notatki z bloga Luca Trevisan , Lemma 3, stwierdza się jako . Czy jest to najlepiej znane pod względem zależności od n ? Będę szczególnie wdzięczny za odniesienie do źródła cytowanego!$O(1/\epsilon^4 n \log n)$$n$

Powiązane pytanie: jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Kushilevitz-Mansour?

Pytanie wydaje się nieco niedoprecyzowane w tym sensie, że nie określiło pożądanego prawdopodobieństwa błędu procedury. Zakładając, że jedno oznacza stałe prawdopodobieństwo błędu, powyższe jest rzeczywiście najlepsze, jakie znam. Szczegółowa dyskusja znajduje się w rozdziale 2.5.2.4 mojej książki „The Foundations of Cryptography - Volume 1” dostępnej na stronie http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

POWYŻEJ JEST ŹLE. ZOBACZ PRAWIDŁOWĄ ODPOWIEDŹ PONIŻEJ.

$O(n \log^3(1/\epsilon))$$n^2$$n$$\Omega(\epsilon^2)$$2/3$${\tilde O}(n/\epsilon^2)$