Goldman and Kearns [{\em J. Comput. Syst. Sci.,} 50 (1995), pp. 20-31] have introduced a variant of the standard on-line learning model in which a helpful teacher selects a sequence of labeled instances for the learner. We answer two open problems posed by Goldman and Kearns about this teaching model. The first problem is whether the class of polynomial-size monotone circuits has polynomial teaching dimension; we provide a strong negative answer by showing that the class of polynomial-size monotone formulae has exponential teaching dimension. We also exhibit a natural concept class (intersections of two halfspaces) for which it is NP-hard for a teacher to compute the length of an optimal teaching sequence, answering another problem. These results indicate strong limits on efficient teachability in the Goldman-Kearns model.
Postscript or
pdf.