CS369N: Beyond Worst-Case Analysis

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).)
  • Under construction. 3 out of 5 problems posted so far. A fourth will be posted shortly. The fifth relates to the December 1 lecture and will be posted around that time.

Lecture notes: 1-2 weeks after each lecture the instructor will send a rough draft of lecture notes out to the email list. Eventually, edited versions will be posted to this website. Even further in the future (but hopefully before the year's end) wordpress-style versions will be published.

Tentative schedule and references: (Under construction.)

• Week 1 (Sept 25): Class cancelled for the Randomized Algorithms: Theory and Applications workshop dedicated to the memory of Rajeev Motwani.

• Week 2 (Oct 2): Instance optimality. References:
  • Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS '03.
  • Afshani/Barbay/Chan, Instance-optimal geometric algorithms, FOCS '09.

• Week 3 (Oct 9): Models of data in competitive online paging/caching. General reference:
  • Chapter 5 of the textbook Online Computation and Competitive Analysis by Borodin/El-Yaniv.
  "First-generation" research papers discussed in class:
  • 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.
  "Second-generation" results, some of which are touched on in the homeworks, are surveyed in:
  • Angelopoulos/Schweitzer, Paging and List Update under Bijective Analysis, SODA '09.

• Week 4 (Oct 16): 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 5 (Oct 23): More on clustering and graph partitioning with plannted solutions. Learning mixtures of disributions. Planted and semirandom models. Primary 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 6 (Oct 30): 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 7 (Nov 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 8 (Nov 13): 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.
  General references on smoothed analysis:
  • Spielman/Teng, Smoothed analysis: an attempt to explain the behavior of algorithms in practice, CACM '09.
  • The smoothed analysis homepage.

• Week 9 (Non-standard date: Thursday Nov 19, 10-12:30, 380-380F): 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 '02.

• Week 10 (Non-standard date: Tuesday Dec 1, 10-12:30, Gates 498): From probabilistic (or Bayesian) environments to instance optimality. References: