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 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html


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

  • 2
    $\begingroup$ 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... $\endgroup$ – Oded Goldreich Jun 1 '14 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.