Mathematical Toolkit - Spring 2013


MW 1:30-2:50, TTIC Room 530

Office Hours: Monday 3-4

Instructor: Madhur Tulsiani


Mailing List:


The goal of this course is to collect and present important mathematical tools used in different areas of theoretical computer science. We intend to cover the following topics:

  • Discrete probability: Markov’s inequality, Chebyshev and Chernoff bounds.
  • Gaussian probability and dimension reduction.
  • Spectral graph theory.
  • Fourier analysis on the hypercube.
  • LP relaxations and duality.
  • Multiplicative updates method.

The course will have 2-3 homeworks. Each student will also be expected to scribe 1-2 lectures.



  • 4/1: Probability spaces, Schartz-Zippel lemma and applications, random variables and expectations.
  • 4/3: Expectations of random variables, randomized algorithms and derandomization using conditional expectations, the probabilistic method (using first moments).
  • 4/8: Markov's and Chebyshev's inequalities, weak law of large numbers, threshold phenomena in random graphs.
  • 4/10: Chernoff/Hoeffding bounds, Max-Cut in random graphs, randomized routing on the hypercube.
  • 4/17: Randomized routing on the hypercube, load balancing, power of two choices.
  • 4/22: Power of two choices (continued). Gaussian random variables, Johnson-Lindenstrauss lemma.
    [Unedited Notes]
  • 4/24: Fast rank-k approximation for matrices using dimension reduction, Karger-Motwani-Sudan algorithm for approximate graph coloring using Gaussian projections.
    [Unedited Notes]
  • 4/29: KMS algorithm wrap-up, introduction to spectral graph theory.
    [Unedited Notes]
  • 5/1: Expansion of a graph and Cheeger's inequality, higher-order generalizations of Cheeger's inequality.
    [Unedited Notes]
  • 5/6: Random walks on graphs, introduction to expander graphs, application to de-randomization.
    [Unedited Notes]
  • 5/8: Spielman's explicit expander-construction using line graphs.
    [Unedited Notes]
  • 5/13: Introduction to Fourier analysis, linearity testing.
    [Unedited Notes]
  • 5/15: Eigenvalues and eigenvectors for the hypercube and Calyley graphs on {0,1}^n, characterization of sparse balanced cuts on the hypercube, construction of expanders using epsilon-biased sets.
  • 5/20: The Goldreich-Levin theorem, learning decision trees using membership queries.
  • 5/22: Learning decision trees wrap-up. Introduction to linear programming, approximation algorithms and LP duality.
  • 5/29: More on LP duality, max-flow/min-cut duality.
  • 6/3: Hall's theorem, the linear programming bound for codes.
  • 6/5: Learning from experts using weighted majority, the multiplicative updates method, Plotkin-Shmoys-Tardos framework for solving LPs.