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