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
A standard method of measuring the algorithmic efficiency is to provide a worstcase running time bound for it. However, there are certain cases where such an analysis is too pessimistic and may fail to capture problemspecific structure that leads our algorithms to run much faster in practice. In this reading group, we will survey analytical models that move beyond worstcase analysis, how they are applied to different problems, and their respective benefits and drawbacks. Throughout this semester, we will discuss papers and notes on averagecase analysis for random instances, analysis of distributions with "planted" solutions, semirandom models which combine random and adversarial choices, averagecase through smoothed analysis, instance stability, and analytical regimes for online algorithms.
Refer here for a detailed list.
Here are various notes on odd topics that were skimmed over during the course of the reading group.
Date  Topic  Resources 

8/28/2018 
Preliminary logistics meeting — Soda 373 @ 6:30pm

Meeting minutes 
9/10/2018 
Probability and Linear Algebra presented by Antares, Hermish — Cory 293 @ 5:30pm

Scribe notes 
9/17/2018 
Largest Clique in a Random Graph presented by James, William, Zod — Cory 293 @ 5:30pm

Scribe notes 
9/24/2018 
Planted Clique via spectral algorithm presented by William, Zod — Soda 373 @ 5:30pm

Scribe notes
iPython notebook 
10/1/2018 
Semidefinite Programming presented by Vishnu — Cory 293 @ 5:30pm 
Scribe notes 
10/8/2018 
Planted Clique via Semidefinite Programming presented by Wilson — Soda 341A @ 5:30pm

Scribe notes 
10/15/2018 
Stochastic Block Model (1) presented by Antares, Nate, Vishnu — Cory 293 @ 5:30pm 
Scribe notes
iPython notebook 
10/22/2018 
Stochastic Block Model (2) presented by Antares, Haaris — Cory 293 @ 5:30pm 
Scribe notes
iPython notebook 
10/29/2018 
BWCA noting and coding workday — Cory 293 @ 5:30pm


11/5/2018 
BiluLinial Stability and kMedians presented by Antares, Saam — Cory 293 @ 5:30pm

Scribe notes coming soon 
11/12/2018 
Administrative holiday — no meeting


11/19/2018 
School closure due to smoke — no meeting


11/26/2018 
BalcanBlumGupta Stability and kMedians presented by James — Cory 293 @ 5:30pm

Scribe notes 
12/7/2018 
Theory Fest! Online Algorithms presented by Antares, Brian, Haaris, Hermish, Wilson — Cory 293 @ 4:00pm

Scribe notes coming soon 