This projects seeks efficient algorithms for learning complex concepts from examples and other kinds of information. A major focus on the "other kinds of information" that may serve to reduce the computational difficulty of learning complex concepts, including queries to a teacher, advantageous order of presentation of examples, the presence of related concepts, and constraits imposed by real-world situations (e.g., robot navigation, language learning). New models of interaction between a teacher and a learner will be developed and explored. Techniques from computational complexity, the theory of automata and formal languages, the analysis of algorithms, and cryptography will be used to define and explore models of efficient learnability.
