Fall 2018: Beyond Worst Case Analysis

Location: Cory 293 (there are some exceptions where we will meet elsewhere such as Soda 373)
Time: Every Monday at 5:30 pm
Logistics: Please join our emailing list here to stay up to date with our events. We will also be holding special events so do check the calendar below.
Files: Scribe note template

About this Group

A standard method of measuring the algorithmic efficiency is to provide a worst-case running time bound for it. However, there are certain cases where such an analysis is too pessimistic and may fail to capture problem-specific structure that leads our algorithms to run much faster in practice. In this reading group, we will survey analytical models that move beyond worst-case analysis, how they are applied to different problems, and their respective benefits and drawbacks. Throughout this semester, we will discuss papers and notes on average-case analysis for random instances, analysis of distributions with "planted" solutions, semi-random models which combine random and adversarial choices, average-case through smoothed analysis, instance stability, and analytical regimes for online algorithms.

Topics Outline

Refer here for a detailed list.

  • Background review in Discrete Probability and Linear Algebra
  • Random instances, planted distributions, and semi-random models
    • Cliques in a random graph
    • Planted cliques in random graphs
    • Finding partitions in the Stochastic Block Model
  • Smoothed analysis of the Simplex algorithm
  • Instance stability
    • Stability as defined by Bilu and Linial
    • Stability as defined by Balcan, Blum and Gupta
  • Online algorithms
    • Secretary problem and paging
    • Experts and Multiplicative Weights

Additional Resources

  • Luca Trevisan's CS294-134 Beyond Worst Case Analysis
  • Tim Roughgarden's CS264 Beyond Worst Case Analysis (Winter 2017)
  • Ankur Moitra's 6.854 (MIT's CS270 equivalent). It even includes a link to lecture videos.
  • Bootcamp from the Simons Institute's Fall 2016 program on Algorithms and Uncertainty

Loose Ends

Here are various notes on odd topics that were skimmed over during the course of the reading group.

  • Coming soon...

Readings and Meetings

Date Topic Resources

Preliminary logistics meeting — Soda 373 @ 6:30pm

  • Discussed plans for weekly meetings
  • Considered a number of semester long projects
  • Discussed topics regarding UGTCS student group
Meeting minutes

Probability and Linear Algebra presented by Antares, Hermish — Cory 293 @ 5:30pm

  • Suggested readings for Discrete Probability
    • Review notes covering basic discrete probability and using Markov, Chebyshev inequalities to bound the probability of bad events.
    • More extensive discussion covering discrete and continuous probability.
  • Suggested readings for Linear Algebra
    • Chapter 1 of Luca's book on expander graphs covering real symmetric matrices and the variational characterization of eigenvalues.
    • A more extensive discussion used in Stanford's CS229
Scribe notes

Largest Clique in a Random Graph presented by James, William, Zod — Cory 293 @ 5:30pm

  • These notes on proving that the max clique is 2log(n) w.h.p and a greedy algorithm for finding a log(n) clique.
Scribe notes

Planted Clique via spectral algorithm presented by William, Zod — Soda 373 @ 5:30pm

  • These notes on using spectral methods to find a planted clique of size sqrt(n).
  • The original paper on the AKS planted clique algorithm.
  • Try some exercises
    • Implement the spectral algorithm and test it on this instance
    • Show how recover a planted dense subgraph of size k > c sqrt(n), where c is a sufficiently large constant. In this model, a set S of k vertices is randomly chosen, then edges within S are chosen each with probability 3/4, and all other edges are chosen with probability ½
Scribe notes
iPython notebook

Semidefinite Programming presented by Vishnu — Cory 293 @ 5:30pm

  • These notes from the original BWCA course.
  • These notes from Ankur Moitra's 6.854.
Scribe notes

Planted Clique via Semidefinite Programming presented by Wilson — Soda 341A @ 5:30pm

  • These notes from Tim Roughgarden's CS264 (portion on planted clique).
Scribe notes

Stochastic Block Model (1) presented by Antares, Nate, Vishnu — Cory 293 @ 5:30pm

  • These notes on approximately finding partitions using spectral methods.
  • These notes from Dan Spielman's course on spectral graph theory.
Scribe notes
iPython notebook

Stochastic Block Model (2) presented by Antares, Haaris — Cory 293 @ 5:30pm

  • These lecture notes (note 1 and note 2) on exactly recovering communities with an SDP based algorithm.
Scribe notes
iPython notebook

BWCA noting and coding workday — Cory 293 @ 5:30pm

  • Help build various iPython notebooks showcasing the algorithms we have seen so far this semester.

Bilu-Linial Stability and k-Medians presented by Antares, Saam — Cory 293 @ 5:30pm

Scribe notes coming soon

Administrative holiday — no meeting

  • Have a relaxing day off!

School closure due to smoke — no meeting

  • Stay safe everyone!

Balcan-Blum-Gupta Stability and k-Medians presented by James — Cory 293 @ 5:30pm

  • These lecture notes on approximation-stable k-Medians clustering.
Scribe notes

Theory Fest! Online Algorithms presented by Antares, Brian, Haaris, Hermish, Wilson — Cory 293 @ 4:00pm

Scribe notes coming soon