CS4252: Introduction to
Computational Learning Theory
Summer 2005
Instructor: Rocco Servedio
Class Manager: Andrew Wan
Email: atw12@columbia.edu


The question "Can machines learn from experience?" is one that has fascinated people for a long time. Over the past few decades, many researchers in computer science have studied this question from a range of applied and theoretical perspectives. This course will give an introductiion to some of the central topics in computation learing theory. We will study well-defined mathematical models of learning in which it is possible to give precise and rigorous analyses of learning problems and learning algorithms. A big focus of the course will be the computational efficiencey of learning in these models. We'll develop computationally efficient algorithms for certain learning problems, and will show why efficient algorithms are not likely to exist for other problems.


This is a preliminary list of "core" topics. Other topics may be covered as well depending on how the semester progresses. Some topics will take more than one lecture.


You should be familiar with the following topics.