Location: Soda 373 (there will be some exceptions, check the calendar below)
Time: Every Monday at 6:00pm
Logistics: Please join our emailing list to stay up to date with our meetings and events
Files: scribe note template
Modern algorithm design and analysis often samples techniques from a common toolbox of analytic techniques. These may include using concentration inequalities to bound error probabilities or using linear programming to relax intractable problems. This reading group, adapted from courses of similar names (see links below), will provide a tapas style introduction to these tools. Our goal will be to cover argument styles and constructions from a diverse set of mathematical studies. Building off of tools and ideas from CS70 and CS170, we will discuss topics in linear algebra, probability theory, optimization, convex geometry, information theory, and more as well as a examples of each that demonstrate their applicability towards solving a variety of combinatorial problems. Some include:
The examples we encounter along the way will be rigorous yet succinct, and hopefully reveal connections between various problems that one might not have expected!
Refer to this document for a more detailed list of topics.
Date  Topic  Resources 

2/2/2019  Preliminary logistics meeting — Soda 320 @ 5:30pm


2/4/2019  The Dimension Argument presented by Jonathan — Cory 293 (different room) @ 6:00pm


2/11/2019  The Probabilistic Method presented by Nate — Soda 373 @ 6:00pm


3/4/2019  Spectral Graph Theory 1 presented by Antares and Zhiwei — Soda 373 @ 6:00pm

Full scribe notes in progress… Antares’s scribe notes (draft) 
3/11/2019  Spectral Graph Theory 2 presented by Alex and Robert — Soda 373 @ 6:00pm 

3/18/2019  Electrical Flows presented by Druv and Zhiwei — Soda 373 @ 6:00pm

Scribe notes in progress… 
4/1/2019  Randomized Rounding of SDPs presented by Ida and Zod — Soda 373 @ 6:00pm


4/15/2019  High Dimensional Convex Geometry presented by Antares and Jon — Soda 373 @ 6:00pm


4/22/2019  Information Theory presented by Jon — Soda 373 @ 6:00pm 

4/29/2019  Derandomization and Expanders presented by Jonathan — Soda 373 @ 6:00pm


5/6/2019  Boolean Analysis and Property Testing presented by Alex, Debayan, and Kobe — Soda 373 @ 6:00pm 

5/10/2019  Quantum Computing presented by Robert and Vishnu — Soda 373 @ 5:00pm
