This research project addresses problems in computational learning theory, the investigation of algorithms and formal methods for various natural and artificial learning systems. The following specific topics are addressed in this project: the complexity of on-line learning with an oblivious environment; the power of randomization for on-line learning; design of space-efficient algorithms for on-line learning; design and analysis of error-tolerant on-line learning algorithms; on-line learning of definitions in fragments of first order predicate logic; analysis of the computational power of common computational neural network models; design and analysis of learning algorithms for concept classes on neural networks of depth 2.
