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

**Teaching Assistants:**

- Rishi Gupta (Office hours: Wednesdays 3:30-5:30, Gates 460. Email: rishig "at" cs.stanford.edu)

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

- Lecture 1 (Introduction): Video Notes (beta version)
- Lecture 2 (Instance-Optimality): Video Notes (beta version)
- Lecture 3 (Resource Augmentation): Video Notes (beta version)
- Lecture 4 (Parameterized Paging): Video Notes (beta version)
- Lecture 5 (Recoverable Value): Video Notes (beta version)
- Lecture 6 (Stable Clustering): Video Notes (beta version)
- Lecture 7 (Single-Link++): Video Notes (beta version)
- Lecture 8 (Recovering Graphs Cuts) Video Notes (beta version)
- Lecture 9 (Compressive Sensing) Video Notes (beta version)
- Lecture 10 (Planted Graph Models) Video Notes (beta version)
- Lecture 11 (LP Decoding) Video Notes (beta version)
- Lecture 12 (LP Decoding/Smoothed Simplex) Video (see Lectures 11 and 13 for notes)
- Lecture 13 (Smoothed Local Search) Video Notes (old, to be updated)
- Lecture 14 (Smoothed Pareto Curves) Video Notes (beta version)
- Lecture 15 (Pseudopoly = Smoothed Poly) Video Notes (beta version)
- Lecture 16 (Hashing + Pseudorandom Data) Video Notes (old, to be updated)
- Lecture 17 (Self-Improving Algorithms) Video Notes (old, to be updated)
- Lecture 18 (Pricing Using Samples) Video Notes (beta version)
- Lecture 19 (Random Permutations) Video Notes (beta version)
- Lecture 20 (Distributions=>Instance-Optimality) Video Notes (beta version)
- The CS264 Top 10 List

**Homeworks:**

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

- 2011 Workshop on Beyond Worst-Case Analysis, at Stanford. Note videos for all talks and the panel discussion are online.
- 2014 Workshop on Analysis of Algorithms Beyond the Worst Case at Dagstuhl, Germany. (No talk videos, unfortunately.)

**Detailed schedule and references:**

**Lecture 1:**Three motivating examples. Pros and cons of worst-case analysis. Instance optimality. References:- Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS '03.

**Lecture 2:**Instance optimality in computational geometry. References:- Afshani/Barbay/Chan, Instance-optimal geometric algorithms, FOCS '09.

**Lecture 3:**The algorithm analysis toolbox. Online paging. Resource augmentation. Loose competitiveness. References:- Sleator/Tarjan, Amortized efficiency of list update and paging rules, CACM '85.
- Young, On-Line File Caching, SODA '98/Algorithmica '02.

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

**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. Main reference:- 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.
- Andrew Goldberg on computing shortest paths in networks with low "highway dimension".
- A taste of fixed-parameter tractability, via the Vertex Cover problem (Coursera videos): Part 1 and Part 2

**Lecture 6:**Stable clustering, part 1. The k-median problem and the BBG algorithm. Reference:- Balcan/Blum/Gupta, Clustering under Approximation Stability, JACM '13.

- Avrim Blum on stable clustering.

**Lecture 7:**Stable clustering, part 2. Single-link++ recovers the optimal solution in perturbation-stable k-median instances. References:- Awasthi/Blum/Sheffet, Center-based Clustering under Perturbation Stability, IPL '11.

**Lecture 8:**Exact recovery. When are linear programs exact? Case studies: the minimum s-t cut and multiway cut problems. References:- Makarychev/Makarychev/Vijayaraghavan, Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut, SODA '14.

**Lecture 9:**A taste of compressive sensing. Finding sparse solutions to underdetermined linear systems. When does l1-minimization work? References:- Section 4.5 of Moitra's lecture notes.
- Lee's blog posts on the fact that random subspaces are almost Euclidean with high probability: Part 1 and Part 2.

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

**Lecture 11:**LP decoding of LDPC codes. References:- Feldman/Malkin/Servedio/Stein/Wainwright, LP Decoding Corrects a Constant Fraction of Errors, IEEE Transactions on Information Theory, 2007.

**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). References:- Viderman, LP decoding of expander codes: a simpler proof, 2012.

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

- Dan Spielman on smoothed analysis.
- Shang-Hua Teng 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:- Englert/Roeglin/Voecking, Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP, SODA '07 and Algorithmica.

**Lecture 14:**Smoothed analysis of Pareto curves. Application: the Knapsack problem has polynomial smoothed complexity. Reference for lecture:- Beier/Roeglin/Voecking, The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization, IPCO '07.

- Ankur Moitra on smoothed analysis of Pareto curves.

**Lecture 15:**For binary optimization problems, polynomial smoothed complexity <=> (Las Vegas randomized) pseudopolynomial worst-case complexity. Reference for lecture:- Beier/Voecking, Typical Properties of Winners and Losers in Discrete Optimization, STOC '04/SICOMP '06.

**Lecture 16:**Pseudorandom data and hashing. Why simple hash functions work as well as fully random ones in practice. References:- Mitzenmacher/Vadhan, Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream, SODA '08.
- See also this later version, with Chung.

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

**Lecture 17:**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.

**Lecture 18:**Pricing to maximize expected revenue with an unknown distribution. References:- Dhangwatnotai/Roughgarden/Yan, Revenue Maximization with a Single Sample, EC '10.
- Huang/Mansour/Roughgarden, Making the Most of Your Samples, 2014.

- Qiqi Yan on prior-independent auctions.
- Your instructor on prior-independent auctions.

**Lecture 19:**The random permutation model. Applications to online network design and secretary problems. References:- Garg/Gupta/Leonardi/Sankowski, Stochastic Analyses for Online Combinatorial Optimization Problems, SODA '08.
- Babaioff/Immorlica/Kleinberg, Matroids, Secretary Problems, and Online Mechanisms, SODA '07.

- 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. References:- Blum/Mansour, Learning, Regret Minimization, and Equilibria, Sections 4.3-4.4.2 (in the AGT book).
- Kalai/Vempala, Efficient Algorithms for On-line Optimization, JCSS '05.