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
8/28/2018	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
9/10/2018	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
9/17/2018	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
9/24/2018	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
10/1/2018	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
10/8/2018	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
10/15/2018	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
10/22/2018	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
10/29/2018	BWCA noting and coding workday — Cory 293 @ 5:30pm Help build various iPython notebooks showcasing the algorithms we have seen so far this semester.
11/5/2018	Bilu-Linial Stability and k-Medians presented by Antares, Saam — Cory 293 @ 5:30pm These lecture notes on perturbation-stable k-Medians clustering. For extra reading, consider checking out these notes on… perturbation stability in minimum s-t cut and minimum multiway cut perturbation stability in maxcut	Scribe notes coming soon
11/12/2018	Administrative holiday — no meeting Have a relaxing day off!
11/19/2018	School closure due to smoke — no meeting Stay safe everyone!
11/26/2018	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
12/7/2018	Theory Fest! Online Algorithms presented by Antares, Brian, Haaris, Hermish, Wilson — Cory 293 @ 4:00pm These notes on competitive analysis, the secretary problem and caching. These notes on experts and multiplicative weight update. For extra reading, checking out Further notes on caching. These lectures from Matt Weinberg, Seffi Naor, Nicolò Cesa-Bianchi and Tim Roughgarden Stay afterwards for the BWCA End of Year social!	Scribe notes coming soon