Introduction to Computational Learning Theory (COMP SCI 639)

Spring 2023

This course will focus on developing the core concepts and techniques of computational learning theory. We will examine the inherent abilities and limitations of learning algorithms in well-defined learning models. Specifically, the course will focus on algorithmic problems in supervised learning. The goal of supervised learning is to infer a function from a set of labeled observations. We will study algorithms for learning Boolean functions from labeled examples in a number of models (online learning, PAC learning, SQ learning, learning with noise, etc.).

Course Information


Mathematical maturity. Background in undergraduate algorithms.

Course Outline

Here is an outline of the course material:


Course Evaluation

Homework Assignments: There will be 5 to 6 homework assignments that will count for 60% of the grade. The assignments which will be proof-based, and are intended to be challenging. Collaboration and discussion among students is allowed, though students must write up their solutions independently.

Exam: There will be a take-home exam that will count for 30% of the grade.

The remaining part of the grade will be based on class participation (10%).


The textbook for this course is:

An additional textbook (available online) we will use is: