CS369N: Beyond Worst-Case Analysis

Instructor: Tim Roughgarden (Office hours: by appointment in Gates 462)

Time/location: 1:15-2:30 PM on Tuesdays and Thursdays in McCullough 122.

Course description: Theoretical work in the design and analysis of algorithms commonly measures the performance of an algorithm (its running time and/or solution quality) using worst-case analysis. For many problems, the worst-case analysis framework successfully identifies non-trivial and useful algorithms (as seen in any undergraduate algorithms textbook). This course is motivated by problems for which traditional worst-case analysis is *not* useful, either because it fails to differentiate meaningfully between different solutions, or because it recommends an intuitively "wrong" solution over the "right" one. The plan is to study systematically alternatives to traditional worst-case analysis that nevertheless enable rigorous and robust guarantees on the performance of an algorithm.

Tentative 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 will be drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, and auction theory.

Prerequisites: CS154N and CS161, or equivalents. CS261 will be very helpful but is not strictly required.

Related workshop: We recently (September 19-21, 2011, at Stanford) had a Workshop on Beyond Worst-Case Analysis. Note videos for all talks and the panel discussion are online.

Course requirements: Students will have a choice between problem sets and a take-home final; a theoretical research project; and an empirical research project.

Students doing projects instead of PS#2-4 should hand in their report to the instructor by noon on December 16th.

Syllabus and references:

Part I: Novel Worst-Case Bounds

Part II: Deterministic Data Models

Part III: Probabilistic Data Models