CS264: Beyond Worst-Case Analysis
Roughgarden (Office hours: Mondays after class, Gates 474.)
(Office hours: Wednesdays 3:30-5:30, Gates 460.
Email: rishig "at" cs.stanford.edu)
2:15-3:30 PM on Mondays and Wednesdays in 200-219.
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,
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
Prerequisites: undergraduate algorithms (CS161, or equivalent).
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
- Submit your homeworks here.
- A LaTeX template that you can use to
type up solutions. Here
and here are good
introductions to LaTeX.
- Homework #1 (Out Wed 9/24, due midnight Wed 10/1.)
- Homework #2 (Out Wed 10/1, due midnight Wed 10/8.)
- Homework #3 (Out Wed 10/8, due midnight Wed 10/15.)
- Homework #4 (Out Wed 10/15, due midnight Wed 10/22.)
- Homework #5 (Out Wed 10/22, due midnight Wed 10/29.)
- Homework #6 (Out Wed 10/29, due midnight Wed 11/5.)
- Homework #7 (Out Wed 11/5, due midnight Wed 11/12.)
- Homework #8 (Out Wed 11/12, due midnight Wed 11/19.)
- Homework #9 (Out Wed 11/19, due midnight Wed 12/3.)
- Homework #10 (Out Wed 12/3, due midnight Wed 12/10.)
Related workshops: Since this course debuted in 2009, there have been a couple of workshops on the topic:
Detailed schedule and references:
- Lecture 1:
Three motivating examples. Pros and cons of worst-case analysis.
- Lecture 2: Instance optimality in computational geometry.
- Lecture 3:
The algorithm analysis toolbox.
Online paging. Resource augmentation.
- Lecture 4:
Case studies in parameterized analysis (Part 1).
Parameterizing page sequences by their locality.
Optimal page fault bounds for LRU.
Rigorously separating LRU and FIFO.
Related videos (from the 2011 workshop on BWCA):
- Lecture 5:
Case studies in parameterized analysis (Part 2).
Approximation algorithms for the maximum-weight independent
set problem. The recoverable value.
A tour d'horizon of common input- and solution-based parameters
for different types of data.
- Lecture 6: Stable clustering, part 1.
The k-median problem and the BBG algorithm.
- Lecture 7: Stable clustering, part 2.
Single-link++ recovers the optimal solution in perturbation-stable k-median instances.
- Lecture 8: Exact recovery.
When are linear programs exact? Case studies: the minimum s-t cut and multiway cut problems.
- Lecture 9:
A taste of compressive sensing.
Finding sparse solutions to underdetermined linear systems.
When does l1-minimization work?
- Lecture 10:
Planted and semirandom models for clique and graph partitioning.
- Lecture 11:
LP decoding of LDPC codes.
- Lecture 12:
Finish LP decoding of LDPC codes (see Lecture 11 notes).
Introduction to smoothed analysis (see Lecture 13 notes).
Spielman-Teng from 30000 feet (see Lecture 13 notes).
General references on smoothed analysis:
- Lecture 13:
Smoothed analysis of local search heuristics. Case study: the 2OPT
local search heuristic for TSP in the plane.
Reference for lecture:
- Lecture 14:
Smoothed analysis of Pareto curves. Application: the Knapsack problem
polynomial smoothed complexity.
Reference for lecture:
- Lecture 15:
For binary optimization problems,
polynomial smoothed complexity <=> (Las Vegas randomized)
pseudopolynomial worst-case complexity.
Reference for lecture:
- Lecture 16:
Pseudorandom data and hashing. Why simple hash functions work as well
as fully random ones in practice.
- Lecture 17: Self-improving algorithms.
- Lecture 18: Pricing to maximize
expected revenue with an unknown distribution.
- Lecture 19: The random permutation model.
Applications to online network design and secretary problems.
- Anupam Gupta on stochastic analyses of network design problems.
- Lecture 20:
From unknown input distributions to restricted instance optimality.
Case study: regret bounds for online decision-making.