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

14

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/ϵ4nlogn)n

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

Grigorij Jarosławcew
źródło

Odpowiedzi:

19

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(nlog3)(1/ϵ))n2)nΩ(ϵ2))2)/3)O~(n/ϵ2))

Oded Goldreich
źródło
2
Historia (mojego błędu): Widząc to pytanie, po prostu spojrzałam na wspomnianą sekcję, źle przeczytałam oświadczenie (z powodu pośpiechu) i po prostu odpowiedziałam, co myślisz. Później niejasno przypomniałem sobie, że kiedyś zadano mi to samo pytanie i udzielono odmiennych odpowiedzi. Więc sprawdziłem dokładniej. Lekcje (które powinienem był znać): Nie rób rzeczy w pośpiechu; nie działaj wo myśląc ...
Oded Goldreich