COMP_SCI 496: Mathematical Toolkit

Quarter Offered

Spring : F 10-1 ; Makarychev


Undergrad students who want to take the course should be approved by the instructor.


This seminar is primarily intended for graduate and advanced undergraduate students who plan to do research in theoretical computer science. We will discuss various math topics in areas such as probability, analysis, and linear algebra and examine how these concepts can be used in theoretical computer science.

Here is a sample list of topics for this course:

  • One dimensional and multivariate Gaussian distributions. Central Limit Theorem. Chernoff bounds. Concentration of measure. Gaussian correlation conjecture. Applications to approximation algorithms and discrepancy minimization.
  • Poisson distribution. Power of two choices. Rich-get-richer model.
  • Probabilistic method.
  • Filtration. Martingales. Stopping time. Concentration inequalities for martingales. Graph exposure martingales.
  • Lovasz local lemma.
  • Convex and Metric Geometry. Metric embeddings. Dimension reduction. Johnson–Lindenstrauss transform. Bourgain’s theorem. Lp spaces. Brunn—Minkowski theorem.
  • Expanders and spectral graph theory. Cheeger inequality. Graph partitioning and clustering algorithms.
  • Introduction to Fourier analysis on the Boolean cube.

COURSE INSTRUCTOR: Prof. Konstantin Makarychev