@InProceedings{RY95,
  author = 	 { Ronald L. Rivest and Yiqun Lisa Yin },
  title = 	 { Being Taught Can be Faster than Asking Questions },
  pages = 	 { 144--151 },
  doi =          { 10.1145/225298.225315 }, 
  acm =          { 80879 },                 
  booktitle =    { Proceedings of the Eighth Annual Conference on Computational Learning Theory },
  publisher =    { ACM },
  editor = 	 { Wolfgang Maas },
  isbn =         { 0-89791-723-5 },
  date =         { 1995-07 },                  
  OPTyear = 	 { 1995 },
  OPTmonth = 	 { July 5--8, },
  eventtitle =   { COLT'95 },
  eventdate =    { 1995-07-05/1995-07-08 },
  venue =        { Santa Cruz, California },
  abstract =     {
        We explore the power of teaching by studying two on-line learning models:
        teacher-directed learning and self-directed learning.  In both models, the learner
        tries to identify an unknown concept based on examples of the concept presented
        one at a time.  The learner predicts whether each example is positive or negative
        with immediate feedback, and the objective is to minimize the number of prediction
        mistakes.  The examples are selected by the teacher in teacher-directed learning,
        and by the learner itself in self-directed learning.  Roughly, teacher-directed
        learning represents the scenario in which a teacher teaches a class of learners,
        and self-directed learning represents the scenario in which a smart learner
        asks questions and learns by itself.  For all previously studied concept classes,
        the minimum number of mistakes in teacher-directed learning is always larger than
        that in self-directed learning.  This raises an interesting question of whether
        teaching is helpful for all learners including the smart learner.  Assuming the
        existence of one-way functions, we construct concept classes for which the
        minimum number of mistakes is linear in teacher-directed learning but
        superpolynomial in self-directed learning, demonstrating the power of
        a helpful teacher in a learning process.
                 },
}