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
- Tue 9/27: Instance optimality in database search.
References:
- Thu 9/29: Instance optimality in computational geometry.
References:
- Tue 10/4: Online Paging. Resource augmentation.
Loose Competitiveness.
References:
- Thu 10/6: Resource augmentation in selfish routing.
Parameterized analysis and locality of reference in online paging.
References:
Related videos:
- Tue 10/11:
Parameterized analysis. Input-based parameterizations.
Case study: approximate nearest neighbor search in low-dimensional
metric spaces.
- Lecture notes -- maybe someday?
Main reference:
Additional references:
Related video:
- Andrew
Goldberg on computing shortest paths in networks with low
"highway dimension".
- Thu 10/13:
Parameterized analysis. Solution-based parameterizations.
Case study: maximum-weight independent sets.
- Lecture notes -- maybe someday?
Main reference:
Additional reference:
Related videos:
Part II: Deterministic Data Models
- Tue 10/18: Deterministic models of data.
Access graphs in online paging. The k-median problem
with a planted/stable solution.
References:
- Thu 10/20:
The k-median problem with a planted/stable solution (con'd).
References:
Related video:
- Tue 10/25: Stable instances of Max Cut.
References:
Related video:
- Thu 10/27: Stable instances of k-Median.
- Lecture notes --- maybe someday?
References:
Part III: Probabilistic Data Models
- Tue 11/1:
Planted and semirandom models for clique and graph partitioning.
References:
- Thu 11/3: Self-improving algorithms.
References:
Related video:
- Tue 11/8:
From distributional environments to restricted instance optimality.
Case study: regret bounds for online decision-making.
References:
- Thu 11/10:
From distributional environments to restricted instance optimality.
Case study: performance benchmarks for
revenue-maximizing auctions.
References:
- Tue 11/15:
Stochastic optimization. I.i.d. and random permuatation models.
Case study: network design.
- Lecture notes --- maybe someday?
References:
Related video:
- Anupam Gupta on stochastic analyses of network design problems.
- Thu 11/17:
Pseudorandom data and hashing.
References:
Related video:
- Tue 11/29:
Smoothed analysis of local search heuristics.
Reference for lecture:
General references on smoothed analysis:
Related video:
- Thu 12/1:
Smoothed analysis of Pareto curves. Application: Knapsack has
polynomial smoothed complexity.
-
Lecture notes --- maybe someday?
Reference for lecture:
Related video:
- Tue 12/6:
For binary optimization problems,
polynomial smoothed complexity <=> (Las Vegas randomized)
pseudopolynomial worst-case complexity.
-
Lecture notes --- maybe someday?
Reference for lecture:
- Thu 12/8:
Smoothed analysis of linear programming. Spielman-Teng from 30000
feet. Smoothed analysis of the perceptron algorithm.
References for lecture:
Related video: