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

**Teaching Assistant:**
Qiqi Yan
(Office hours: Wednesdays and Thursday 3-4
PM in Gates 460;
email: contact "at" qiqiyan.com)

**Time/location:** 10 AM-12:30 PM on Fridays in Hewlett 101.

**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; models of data (pseudorandomness, locality, diffuse adversaries, etc.); robust distributional analysis; resource augmentation; planted or semi-random graph models. Motivating problems will be drawn from online algorithms, online learning, graph partitioning, scheduling, linear programming, hashing, and auction theory.

Prerequisites: 154N and 161, or equivalents. 261 will be very helpful but is not strictly required.

**Course requirements:** 2-3 difficult problem sets, typically to be solved
in groups.

- Problem Set #1 (Out October 9th, due in class October 23rd.)
- Problem Set #2 (Out October 30th, due in class November 13th.)
- Problem Set #3 (Out November 20, due December 10 (11:30 AM).)

**Lecture notes:**
The good news is that I've finished first drafts of all of the lectures
(around 100 pages total). The bad news is that I don't have many cycles
available to finish editing, add references, etc. I'm posting
the lectures here as I finish them, and hope to be done with them all
some time in October 2010.

- Lecture #1: Instance Optimality
- Lecture #2: Models of Data in Online Paging
- Lecture #3: Deterministic Planted Models for Clustering and Graph Partitioning
- Lecture #4: Probabilistic and Semirandom Planted Models for Clustering and Graph Partitioning
- Lecture #5: Self-Improving Algorithms

**Syllabus and references.**

**Week 1:**Instance optimality. References:- Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS '03.
- Afshani/Barbay/Chan, Instance-optimal geometric algorithms, FOCS '09.

**Week 2:**Models of data in competitive online paging/caching. General reference:- Chapter 5 of the textbook
*Online Computation and Competitive Analysis*by Borodin/El-Yaniv.

- Sleator/Tarjan, Amortized efficiency of list update and paging rules, CACM '85.
- Borodin/Irani/Raghavan/Schieber, Competitive Paging with Locality of Reference, FOCS '91/JCSS '95.
- Irani/Karlin/Phillips, Strongly Competitive Algorithms for Paging with Locality of Reference, SODA '92/SICOMP '96.
- Karlin/Phillips/Raghavan, Markov Paging, FOCS '92/SICOMP '00.
- Lund/Phillips/Reingold, Paging Against a Distribution and IP Networking, FOCS '94/JCSS '99.
- Koutsoupias/Papadimitriou, Beyond Competitive Analysis, FOCS '94/SICOMP '00.

- Angelopoulos/Schweitzer, Paging and List Update under Bijective Analysis, SODA '09.

- Chapter 5 of the textbook
**Week 3:**Deterministic planted models for graph and metric clustering. References:- Bilu/Linial, Are stable instances easy?, ICS '10.
- Balcan/Blum/Gupta, Approximate Clustering without the Approximation, SODA '09.

**Week 4:**More on clustering and graph partitioning with planted solutions. Learning mixtures of distributions. Planted and semirandom models. References:- Dasgupta, Learning mixtures of Gaussians, FOCS '99.
- Arora/Kannan, A polynomial time algorithm to learn a mixture of general gaussians, STOC '01/Annals of Applied Probability '05.
- McSherry, Spectral Partitioning of Random Graphs, FOCS '01.
- Feige/Killian, Heuristics for Semirandom Graph Problems, JCSS '01.

**Week 5:**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.

**Week 6:**Pseudorandom data. 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.

**Week 7:**Smoothed analysis. References for lecture:- Englert/Roeglin/Voecking, Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, SODA '07.
- Blum/Dunagan,
Smoothed
Analysis of the Perceptron Algorithm for Linear Programming, SODA '02.
- Blum's exposition of the perceptron algorithm.

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

**Week 8:**Resource augmentation. References:- Sleator/Tarjan, Amortized efficiency of list update and paging rules, CACM '85.
- Young, On-Line File Caching, SODA '98/Algorithmica '02.
- Roughgarden/Tardos, How Bad Is Selfish Routing?, FOCS '00/JACM '02.
- Kalyanasundaram/Pruhs, Speed is as powerful as clairvoyance, FOCS '95/JACM '00.

**Week 9:**From probabilistic (or Bayesian) environments to instance optimality. Applications to no-regret online decision-making and revenue-maximizing auctions for digital goods. References:- Nisan/Roughgarden/Tardos/Vazirani (eds),
*Algorithmic Game Theory*, Cambridge University, 2007, Sections 4.3-4.4.2 (by Blum/Mansour). - Hartline/Roughgarden, Optimal Mechanism Design and Money Burning, STOC '08.
- Fiat/Goldberg/Hartline/Karlin, Competitive Generalized Auctions, STOC '02.

- Nisan/Roughgarden/Tardos/Vazirani (eds),