Clarifications to [BFJKMR94]
The very last step in the proof of Theorem 12 (the main SQ lower
bound) assumes the learning algorithm is choosing one of the f_i
as its hypothesis.
There are several ways to remove this assumption: probably the
simplest is just to require that the final query of the learning
algorithm be "what is the error rate of my current hypothesis?".
This only adds 1 to the number of queries made, and by making this
change we only need there to be one function f_i remaining.
Last modified: Mon Jun 26 12:10:20 EDT 2006