This research investigates application of theoretical tools to analyze fundamental issues in machine learning, in planning from incomplete information, and in approximation algorithms. In the area of machine learning, one direction is to provide new algorithmic techniques for fast learning when there is much information available about objects but only a small amount is truly relevant. These techniques are potentially useful both for speeding up learning and for automating the process of selecting what information is given to a learning algorithm. Also new algorithms for learning using neural networks are investigated, especially in the difficult case of high dimensional input spaces. Other fundamental research issues examined include relationships between learning and cryptography, and various ways a learner can usefully employ more active approaches. In the domain of on-line planning past work has been on strategies for traveling without a map in scenes with simple types of obstacles, whose performance can be guaranteed to be not too much worse than the best possible, if one had a map of the region. This is expanded to more varied situations, including those where some kinds of partial maps are available. One interesting case is where partial maps are created by previous explorations. Here one can combine ideas of on-line planning and learning.
