W4995-1: Introduction to Computational Learning Theory
Fall 2003


Introduction | Topics | Prerequisites | Grading | Readings | Schedule of Topics | Web Bulletin Board | Problem Sets

Instructor: Rocco Servedio (517 CSC, office hours Wed 1-3pm) Note: for the week of Sept 1-5 Rocco's office hours will be Thursday, Sept 4 from 2-4pm.
Teaching assistants: Andrew Howard (, Office Hours Thur 2-4 CEPSR 6LE5), Risi Kondor (, office hours TBA)
Room: 252 Engineering Terrace
Time: Tues/Thurs 11:00-12:15pm.


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 introduction to some of the central topics in computational learning 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 efficiency of learning in these models. We'll develop computationally efficient algorithms for certain learning problems, and will see why efficient algorithms are not likely to exist for other problems.

List of Topics

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:

Some basic knowledge of the theory of NP-completeness (e.g. Chapter 7 of Sipser or Chapter 34 of CLRS) and of elementary cryptography (e.g. pages 881-887 of CLRS) would be helpful but is not required -- the course will be self-contained with respect to these topics.

Grading and Requirements

The requirements of the course are as follows: The biweekly problem sets will be due on Thursdays by 5:00pm. You are allowed six late days for the semester. Each late day is exactly 24 hours; late days cannot be subdivided -- five minutes late counts as one late day.   For an exception, you must have your undergraduate advisor (for undergrads) or your graduate advisor (for graduate students) contact me.

The problem sets will require you to do proofs. Some problems will be challenging; you are advised to start the problem sets early.  You are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people), as long as you list all discussion partners on your problem set. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem.  In addition, each person must write up their solutions independently;  you may not look at another student's written solutions. You may consult outside materials, but all materials used must be appropriately acknowledged, and you must always write up your solutions in your own words.


The textbook for this course is:

Schedule of Topics

Click here for a preliminary course schedule.

Web Bulletin Board

Click here to get to the course bulletin board.

Problem Sets

Click here to get to the homework page.