Efficient learning algorithms that use additional information in the form of queries to a teacher will be studied, with particular emphasis on the capabilities and limitations of algorithms that use equivalence and membership queries. Techniques from computational complexity, the analysis of algorithms, and cryptography will be applied to narrow the gap between provably efficiently learnable and provably not efficiently learnable classes of concepts. The problem of missing or incorrect answers to queries and their effects on the learnability of various concrete hypothesis classes will be studied. The problem of approximating a distribution by sampling will be studied as a method of extending Valiant's paradigm of "probably approximately correct" identification to problems in which negative examples are absent.
