Spring 2019 — Theorist's Toolkit

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

About this Group

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:

Analyzing hash functions and error correcting codes as sets of linear equations
Modeling random walks using electrical networks
Using entropy to demonstrate that certain subgraphs exist

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!

Topics Outline

Refer to this document for a more detailed list of topics.

Dimension arguments and error correcting codes
The Probabilistic Method
Spectral graph theory
Electrical flows and random graph walks
Randomized rounding of semidefinite programs
High-dimensional convex geometry
Information theory
Expander graphs and applications to derandomization
Boolean analysis and applications to property testing
Quantum computing

Additional Resources

Ryan O’Donnell A Theorist’s Toolkit 2013
Sanjeev Arora’s offering of a similar course for 2002 and 2007 and related notes
Johan Håstad’s Teoretikerns verktygslåda
Madhur Tulsiani’s A Mathematician’s toolkit from 2016 and 2018
Jonathan Kelner’s An Algorithmist’s toolkit from 2007 and 2009

Date	Topic	Resources
2/2/2019	Preliminary logistics meeting — Soda 320 @ 5:30pm Discuss plans for weekly meetings and semester long goals.
2/4/2019	The Dimension Argument presented by Jonathan — Cory 293 (different room) @ 6:00pm Developing elementary linear algebra arguments, and applying them to dispersal of information in polynomials. These notes on the dimension argument and applications to error correcting codes and hashing.	Scribe notes
2/11/2019	The Probabilistic Method presented by Nate — Soda 373 @ 6:00pm Proving the existence of an object with a certain property by proving that a randomly chosen object has that property with positive probability – applications like Ramsey numbers, existence of a large max-cut, size of independent set, graph crossing number, etc. These notes on the probabilistic method. * These notes on the Lovász Local Lemma. * The paper Graphs with Large Girth and Large Chromatic Number by Cheuk To Tsui.	Scribe notes (draft)
3/4/2019	Spectral Graph Theory 1 presented by Antares and Zhiwei — Soda 373 @ 6:00pm Introducing the eigenvalues of a graph’s adjacency matrix, the Laplacian matrix, and variational characterization of eigenvalues. These notes introducing Spectral Graph Theory.	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 Introducing Markov Chains and applying SGT to analyze random walks and mixing times. These notes on Markov chains and mixing times. * These notes on random walks.	Scribe notes (draft)
3/18/2019	Electrical Flows presented by Druv and Zhiwei — Soda 373 @ 6:00pm Analyzing commute time and cover time of a random walk by treating the graph as a network of resistors. These notes on SGT and Electrical Networks.	Scribe notes in progress…
4/1/2019	Randomized Rounding of SDPs presented by Ida and Zod — Soda 373 @ 6:00pm Relaxing MAX CUT to an SDP, and randomly rounding the SDP’s solution back to a near-optimal cut. Chapters 6.1 and 6.2 from The Design of Approximation Algorithms by Williamson and Shmoys, on SDPs and finding large cuts.	Scribe notes (draft)
4/15/2019	High Dimensional Convex Geometry presented by Antares and Jon — Soda 373 @ 6:00pm Using polyhedral combinatorics (in particular, the Brunn-Minkowski Inequality) to sort a partially ordered set. Somehow. Brunn-Minkowski and applications to sorting partially ordered sets in Matousek’s Lectures in Discrete Geometry.	Jon’s notes (draft) Antares’s scribe notes (draft)
4/22/2019	Information Theory presented by Jon — Soda 373 @ 6:00pm Introducing entropy and Kullback-Leibler Divergence, with cool applications in combinatorics and probability. See the scribe notes for a brief introduction to Entropy. * These notes introducing Joint entropy and Chain Rule for Entropy. * These notes with more combinatorial applications.	Scribe notes (draft)
4/29/2019	Derandomization and Expanders presented by Jonathan — Soda 373 @ 6:00pm Introducing Pseudorandom Generators, using them to derandomize “random” algorithms, and their relation to the BPP complexity class. These notes about derandomization. * Chapter 4 from Salil Vadhan’s survey of Pseudorandomness, on expander graphs. * Chapters 8 from Mathematics and Computations by Avi Wigderson, on abstract pseudorandomness.	Scribe notes (draft)
5/6/2019	Boolean Analysis and Property Testing presented by Alex, Debayan, and Kobe — Soda 373 @ 6:00pm Performing Fourier analysis on boolean functions, analyzing their behavior with SGT, and applying it to property testing. These notes introducing Boolean Analysis. * This notes on proving Arrow’s Theorem with Boolean Analysis.	Scribe notes (draft)
5/10/2019	Quantum Computing presented by Robert and Vishnu — Soda 373 @ 5:00pm Mathematical representation of qubits, quantum circuits, and algorithms for quantum machines (Shor’s, search) These notes introducing Quantum computing.	Scribe notes (draft)