**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.

- Problem Set #1 (Out October 6th, due in class October 20th.)
- Problem Set #2 (Out October 25th, due in class November 8th.)
- Problem Set #3 (Out November 8th, due in class November 29th.)
- Problem Set #4 (aka Take-Home Final) (Out December 1st, due to the instructor by noon on December 16th.)

**Tue 9/27:**Instance optimality in database search.- Lecture notes from 2009.

- Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS '03.

**Thu 9/29:**Instance optimality in computational geometry.- Lecture notes from 2009.

- Afshani/Barbay/Chan, Instance-optimal geometric algorithms, FOCS '09.

**Tue 10/4:**Online Paging. Resource augmentation. Loose Competitiveness.- Lecture notes from 2009 on online paging and unedited lecture notes from 2009 on resource augmentation.

- Sleator/Tarjan, Amortized efficiency of list update and paging rules, CACM '85.
- Young, On-Line File Caching, SODA '98/Algorithmica '02.

**Thu 10/6:**Resource augmentation in selfish routing. Parameterized analysis and locality of reference in online paging.- Unedited lecture notes from 2009 (for resource augmentation only).

- Roughgarden/Tardos, How Bad Is Selfish Routing?, FOCS '00/JACM '02.
- Albers/Favrholdt/Giel, On Paging with Locality of Reference, STOC '02/JCSS '05.

- Susanne Albers on locality of reference in competitive analysis.
- Alex Lopez-Ortiz on the parameterized analysis of online algorithms.

**Tue 10/11:**Parameterized analysis. Input-based parameterizations. Case study: approximate nearest neighbor search in low-dimensional metric spaces.- Lecture notes -- maybe someday?

- Krauthgamer/Lee, Navigating nets: Simple algorithms for proximity search, SODA 2004.

- Gupta/Krauthgamer/Lee, Bounded geometries, fractals, and low-distortion embeddings, FOCS 2003.
- Talwar, Bypassing the embedding: algorithms for low dimensional metrics, STOC 2004.

- 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?

- Feige/Reichman, Recoverable Values for Independent Sets, ICALP '11.

- Feige/Immorlica/Mirrokni/Nazerzadeh, PASS Approximation: A Framework for Analyzing and Designing Heuristics, APPROX '09.

- Nicole Immorlica on PASS approximation.
- Ryan Williams on backdoors in SAT instances.

**Tue 10/18:**Deterministic models of data. Access graphs in online paging. The k-median problem with a planted/stable solution.- 2009 lecture notes on online paging and stable k-median.

- Borodin/Irani/Raghavan/Schieber, Competitive Paging with Locality of Reference, FOCS '91/JCSS '95.
- Chapter 5 of the textbook
*Online Computation and Competitive Analysis*by Borodin/El-Yaniv. - Balcan/Blum/Gupta, Approximate Clustering without the Approximation, SODA '09.

**Thu 10/20:**The k-median problem with a planted/stable solution (con'd).- The large cluster case is covered in these 2009 lecture notes.

- Balcan/Blum/Gupta, Approximate Clustering without the Approximation, SODA '09.

- Avrim Blum on stable clustering.

**Tue 10/25:**Stable instances of Max Cut. References:- Bilu/Linial, Are stable instances easy?, ICS '10.

- Amit Daniely on stable Max Cut.

**Thu 10/27:**Stable instances of k-Median.- Lecture notes --- maybe someday?

- Awasthi/Blum/Sheffet, Center-based Clustering under Perturbation Stability, IPL '11.

**Tue 11/1:**Planted and semirandom models for clique and graph partitioning. References:- Feige/Killian, Heuristics for Semirandom Graph Problems, JCSS '01.

**Thu 11/3:**Self-improving algorithms. References:- Ailon/Chazelle/Comandur/Liu, Self-Improving Algorithms, SODA '06.
- Clarkson/Seshadhri, Self-improving Algorithms for Delaunay Triangulations, SCG '08.
- More recent combined version.

- C. Seshadhri on self-improving algorithms.

**Tue 11/8:**From distributional environments to restricted instance optimality. Case study: regret bounds for online decision-making.- Unedited lecture notes from 2009.

- Nisan/Roughgarden/Tardos/Vazirani (eds),
*Algorithmic Game Theory*, Cambridge University, 2007, Sections 4.3-4.4.2 (by Blum/Mansour). - Kalai/Vempala, Efficient Algorithms for On-line Optimization, JCSS '05.

**Thu 11/10:**From distributional environments to restricted instance optimality. Case study: performance benchmarks for revenue-maximizing auctions.- Unedited lecture notes from 2009.

- Hartline/Roughgarden, Optimal Mechanism Design and Money Burning, STOC '08.
- Goldberg/Hartline/Karlin/Saks/Wright, Competitive Auctions, GEB '06.
- Fiat/Goldberg/Hartline/Karlin, Competitive Generalized Auctions, STOC '02.

**Tue 11/15:**Stochastic optimization. I.i.d. and random permuatation models. Case study: network design.- Lecture notes --- maybe someday?

- Garg/Gupta/Leonardi/Sankowski, Stochastic Analyses for Online Combinatorial Optimization Problems, SODA '08.
- Gupta/Krishnaswamy/Ravi, Online and Stochastic Survivable Network Design, STOC '09.

- Anupam Gupta on stochastic analyses of network design problems.

**Thu 11/17:**Pseudorandom data and hashing. References:- Mitzenmacher/Vadhan, Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream, SODA '08.
- Our proof of the Leftover Hash Lemma followed these notes from a MIT course given by Rubinfeld.

- Michael Mitzenmacher on (among other things) pseudorandom data.

**Tue 11/29:**Smoothed analysis of local search heuristics.- Unedited lecture notes from 2009.

- Englert/Roeglin/Voecking, Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, SODA '07.

- Spielman/Teng, Smoothed analysis: an attempt to explain the behavior of algorithms in practice, CACM '09.
- The smoothed analysis homepage.

- Shang-Hua Teng on smoothed analysis.

**Thu 12/1:**Smoothed analysis of Pareto curves. Application: Knapsack has polynomial smoothed complexity.- Lecture notes --- maybe someday?

- Beier/Roeglin/Voecking, The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization, IPCO '07.

- Ankur Moitra on smoothed analysis of Pareto curves.

**Tue 12/6:**For binary optimization problems, polynomial smoothed complexity <=> (Las Vegas randomized) pseudopolynomial worst-case complexity.- Lecture notes --- maybe someday?

- Beier/Voecking, Typical Properties of Winners and Losers in Discrete Optimization, STOC '04.

**Thu 12/8:**Smoothed analysis of linear programming. Spielman-Teng from 30000 feet. Smoothed analysis of the perceptron algorithm.- Unedited lecture notes from 2009.

- Blum/Dunagan, Smoothed Analysis of the Perceptron Algorithm for Linear Programming, SODA '02.
- Blum's exposition of the perceptron algorithm.

- Dan Spielman on smoothed analysis.