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 mailing list 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

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