|
Schedule
(subject to change) |
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 |
|
|