CS4252: Introduction to
Computational Learning Theory
Spring 2006
Instructor: Rocco Servedio
Class Manager: Andrew Wan
Email: atw12 at columbia dot edu
CONTENTS
ANNOUNCEMENTS
READING

The textbook for this course is

Introduction to Computational Learning Theory, by M. Kearns and U. Vazirani.

This book may be purchased at the Columbia Bookstore or online. Its an excellent book, but several topics we'll cover are not in the book. Pointers to papers which will cover these topics will be given here.

The content for the first 6 lectures will consist of the following two papers. The original paper by Littlestone on the Winnow algorithm can be found here. A survey by Avrim Blum on Online algorithms can be found here. A survey by Robert Schapire on Boosting can be found here.

HOMEWORK See instructions for submitting below. Your problem sets must be turned in as LaTeX documents. If you're unfamiliar with LaTeX, click here for an introduction. All problem sets must be emailed to Andrew Wan by 5:00pm of the due date or they will be considered late. Be sure that your LaTeX source code compiles correctly before you send it; you will be penalized if your code does not compile. Please submit both the LaTeX source code (the file that ends with .tex) and the .ps file.