<p>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 <a href="http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html">http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html</a></p>

<p><strong>THE ABOVE IS WRONG. SEE CORRECTED ANSWER BELOW.</strong></p>

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

CC BY-SA 3.0
2014-06-01T06:48:23.207Z
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
CC BY-SA 3.0
2014-05-31T09:08:50.017Z
2014-06-01T07:21:04.690Z
2014-06-01T07:21:04.690Z
Oded Goldreich
<p>What is the best known query complexity of Goldreich-Levin learning algorithm?
<a href="http://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/">Lecture notes from Luca Trevisan's blog</a>, 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! </p>

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

<cc.complexity-theory><reference-request><lg.learning><fourier-analysis>
Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm
Grigory Yaroslavtsev
# Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

(Asked by: username_0 on 2012-06-30)

What is the best known query complexity of Goldreich-Levin learning algorithm?
[Lecture notes from Luca Trevisan's blog](http://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/), 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?

**Tags:** cc.complexity-theory, reference-request, lg.learning, fourier-analysis

---

## 1 answers

### Answer by username_1 on 2014-05-31. Score: 19 | Accepted answer

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

> **Comments:**
> **username_1**: 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...  

---

