# 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?

The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed the best I know. For a detailed discussion see Sec 2.5.2.4 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

THE ABOVE IS WRONG. SEE CORRECTED ANSWER BELOW.

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).

• The story (of my error): Seeing this question, I just looked at the said section, read the statement wrong (due to haste), and just answered w.o. thinking. Later, I vaguely recalled that I was once asked the same question and answered differently. So, I checked more carefully. Lessons (which i should have known): Don't do things in a haste; don't act w.o. thinking... – Oded Goldreich Jun 1 '14 at 6:48