TTIC 31150/CMSC 31150 - Mathematical Toolkit (Fall 2026)

Lectures: Mon/Wed 3:00-4:20 in TTIC 530

Instructor: Avrim Blum (Office hours: Fri 1:00-1:50 in TTIC 439)

TA: Hirota Kinoshita (Office hours: Mon 4:30-5:30 in TTIC 530)

Course description: The course is aimed at first-year graduate students and advanced undergraduates, and focuses mostly on abstract linear algebra and probabilistic reasoning. We intend to cover the following topics and examples:

Abstract linear algebra: vector spaces, linear transformations, Hilbert spaces, inner product, Gram-Schmidt orthogonalization, eigenvalues and eigenvectors, Singular Value Decomposition, SVD applications.
Discrete probability: events and random variables, Markov, Chebyshev and Chernoff-Hoeffding bounds. Balls and bins problems. Threshold phenomena in random graphs.
Randomized algorithms (e.g., polynomial identity testing, perfect matchings, low-congestion routing).
Gaussian variables, concentration inequalities, dimension reduction.
Additional topics (based on time and interest): Martingales, Markov Chains.

Coursework: The course will have 5 homeworks (50 percent), a midterm (20 percent) and a final (30 percent). There is no textbook for this course. Please see the "Recommended test/readings" section below for some useful references.

Homeworks

Homework 1. Due October 7. Hand in using this dropbox link.

Lecture Notes

09/28: Fields and vector spaces. Linear independence and bases. (slides)
09/30: Vector space applications and linear transformations. (slides)
10/05: Eigenvalues and eigenvectors, inner products. (slides)
10/07: Orthogonality and adjoints. [Hwk1 due]
10/12: The Real Spectral Theorem.
10/14: Singular Value Decomposition.
10/19: SVD for Matrices.
10/21: SVD applications. [Hwk2 due]
10/26: Midterm. You may bring in one sheet of notes.
10/28: Probability basics.
11/02: Probabilistic reasoning.
11/04: Tail inequalities 1. [Hwk3 due]
11/09: Tail inequalities 2.
11/11: Randomized routing. Randomized complexity classes.
11/16: Review
11/18: Probability over uncountably-infinite spaces, Gaussian RVs, Johnson-Lindenstrauss Lemma. [Hwk4 due]
11/30: Random walks on graphs: commute time, cover time and electrical networks.
12/02: Markov chains and rapid mixing. [Hwk5 due]

Recommended texts/readings:

The Linear Algebra a Beginning Graduate Student Ought to Know
(by Jonathan S. Golan)
Linear Algebra Done Right
(by Sheldon Axler)
Compact Operators on Hilbert Space
(by Paul Garrett)
Foundations of Data Science (by Blum, Hopcroft and Kannan)
Lecture notes on foundations of probability by Terry Tao.
Probability and Computing (by Mitzenmacher and Upfal)
The Probabilistic Method (by Alon and Spencer)
High-Dimensional Probability (by Roman Vershynin)