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

Files: scribe note template

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

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)