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!
Powiązane pytanie: jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Kushilevitz-Mansour?
źródło