Schedule (subject to change)
Date Topic Reading Remark
5-Sep Introduction. Overview of course topics.
8-Sep Probability theory review. Events.
12-Sep Random variables, expectation, conditional expectation, Markov inequality.
14-Sep Covariance, variance.
19-Sep Law of large numbers. Chebyshev inequality. Central limit theorem. Ch 3
21-Sep Exponential convergence: Hoeffding bounds. Example: set balancing. How to generate a certain distribution? Ch 4.1
26-Sep Average-case and randomized algorithms. Example: quicksort.
28-Sep Finding a witness. Examples: set balancing, matrix product checking, polynomial identity. Ch 7
3-Oct BPP, RP Ch 1.5
05-Oct Games Ch 2.2
10-Oct Monday schedule, no class Last day to drop without W
12-Oct Yao's minimax theorem
17-Oct Review
19-Oct Midterm exam
24-Oct Packet routing/load balancing (foiling an unknown adversary) Ch 4.2
26-Oct Packet routing end
31-Oct Local query search, fingerprinting
2-Nov Hashing. Ch 8.4
7-Nov Random sampling: Monte-Carlo method. Example: DNF counting. Ch 11
9-Nov Monte-Carlo method continued Ch 11 Nov 10 last day to drop with W
14-Nov Markov chains Ch 6.1-6
16-Nov Invariant distributions, random walk on a graph
21-Nov Eigenvalue gap
22-Nov Thanksgiving, no class
28-Nov Eigenvalue gap continued
30-Nov Sampling a given distribution (Markov Chain Monte-Carlo). Ising model, matchings. Ch 11 and lecture notes
5-Dec Expanders. Existence using the probabilistic method. Ch 6.7
7-Dec BPP amplification using constructive expanders Ch 6.8
12-Dec Overview
19-Dec Final exam 12:30-2:30