|
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 |
|
|