The research component of this project addresses fundamental questions in computational learning theory and complexity. It also addresses specific learning problems that are motivated by practical applications. Computational learning theory provides a framework for the formal study of problems in machine learning. The first goal of this project is to determine necessary and sufficient conditions for learning, prove lower bounds, and design learning algorithms. A focus is on query models of learning, which represent situations in which a learner can ask questions of a teacher or expert, or perform experiments. Emphasis is placed on the effect of forbidden projections on the learnability of investigating Boolean function classes. The project also aims to determine structural properties of languages, in order to prove complexity results. It is directed particularly at resolving open questions concerning automata with powers of both randomness and nondeterminism. Another major goal of the project is to develop algorithms for learning in the presence of irrelevant data. A particular problem is to develop PAC (Probably Approximately Correct) algorithms that are robust in the presence of irrelevant attributes in the following way: they depending on only a few more attributes then the concept they are learning. This problem is theoretical but motivated by practical applications, such as medical diagnosis. In these applications, output hypotheses are used for future prediction (diagnosis). Determining the value of an attribute is expensive perhaps involving a clinical test, and therefore it is desirable to limit the number of attributes whose values must be determined. The educational component of this project includes goals in both undergraduate and graduate education. At the undergraduate level a basic goal is to make theoretical courses accessible and intellectually exciting to a wide range of students. Methods for achieving this goal include the following: preparing handouts, introducing historical and biographical material, presenting algorithms to students using algorithm animation, and using computer lab `algorithm experiments.` At the graduate level, the project includes teaching a graduate course in computational complexity theory with a significant research component. In addition, a reading group in computational learning theory, started last year, will be continued.
