Beste Abfragekomplexität des Goldreich-Levin / Kushilevitz-Mansour-Lernalgorithmus

Was ist die bekannteste Abfragekomplexität des Goldreich-Levin-Lernalgorithmus? Vorlesungsnotizen aus Luca Trevisans Blog , Lemma 3, besagen . Ist dies die bekannteste Abhängigkeit von n ? Besonders dankbar bin ich für den Hinweis auf eine zitierfähige Quelle!$O(1/\epsilon^4 n \log n)$$n$

Verwandte Frage: Was ist die bekannteste Abfragekomplexität des Kushilevitz-Mansour-Lernalgorithmus?

Die Frage scheint insofern etwas unterbewertet, als sie nicht die gewünschte Fehlerwahrscheinlichkeit der Prozedur angibt. Angenommen, man meint konstante Fehlerwahrscheinlichkeit, dann ist das oben Gesagte in der Tat das Beste, was ich kenne. Eine ausführliche Beschreibung finden Sie in Abschnitt 2.5.2.4 in meinem Buch "The Foundations of Cryptography - Volume 1" unter http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

DAS OBEN IST FALSCH. SIEHE BEHOBENE ANTWORT UNTEN.

Prop 2.5.6 im obigen Abschnitt zeigt eine viel bessere Bindung: Der Algorithmus läuft in der erwarteten Zeit mal der Laufzeit des Schätzverfahrens (siehe Verbesserung von n 2 auf n im Kommentar) direkt nach dem Beweis) und ist richtig wp Ω ( ϵ 2 ) . Daher Korrektheit wp 2 / 3 wird in der Zeit (factor) erhaltenen ~ O ( n / ε 2 ) , die in einem gewissen Sinne optimal ist (siehe Exer 30).$O(n \log^3(1/\epsilon))$$n^2$$n$$\Omega(\epsilon^2)$$2/3$${\tilde O}(n/\epsilon^2)$