CS264: Beyond Worst-Case Analysis

Instructor: Tim Roughgarden (Office hours: Mondays after class, Gates 474.)

Teaching Assistants:

Time/location: 2:15-3:30 PM on Mondays and Wednesdays in 200-219.

Piazza site: here

Course description: This course has two intertwined goals. The first goal is to survey several important computational problems for which the traditional worst-case analysis of algorithms is ill-suited, because it fails to differentiate meaningfully between different solutions, recommends an empirically "wrong" solution over the "right" one, or gives excessively pessimistic performance predictions. The second goal is to study systematically alternatives to worst-case analysis that nevertheless enable rigorous and robust guarantees on algorithm performance.

List of topics: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models.

Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, scheduling, linear programming, hashing, and auction theory.

Prerequisites: undergraduate algorithms (CS161, or equivalent).

Course requirements: Weekly exercise sets. Students have the option to substitute a paper-reading project for some of the exercise sets. No late assignments accepted.

Lecture videos and notes

Homeworks:

Related workshops: Since this course debuted in 2009, there have been a couple of workshops on the topic:

Detailed schedule and references: