# Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

What is the best known query complexity of Goldreich-Levin learning algorithm? Lecture notes from Luca Trevisan's blog, Lemma 3, states it as $O(1/\epsilon^4 n \log n)$. Is this the best known in terms of dependence on $n$? I will be particularly grateful for a reference to a citable source!

Related question: what is the best known query complexity of Kushilevitz-Mansour learning algorithm?

Prop 2.5.6 in the aforementioned section proves a much better bound: The algorithm runs in expected time $O(n \log^3(1/\epsilon))$ times the running time of the guessing procedure (see improvement from $n^2$ to $n$ in the comment right after the proof) and is correct w.p. $\Omega(\epsilon^2)$. Hence, correctness w.p. $2/3$ is obtained in time (factor) ${\tilde O}(n/\epsilon^2)$, which is optimal in some sense (see Exer 30).