| # | Date | lecture topic | reading | pset | |
|---|---|---|---|---|---|
| 1 | 01-22 | W | Course Intro (mp4 (2021) ) | Vadhan §1 | |
| 2 | 01-27 | M | Randomized Computation (mp4 (2021) ) | Vadhan §2.1-2.3.1 | |
| 01-28 | T | pset1 (tex/pdf) | |||
| 3 | 01-27 | W | Approx Counting, Random walks (mp4 (2021) ) | Vadhan §2.3.2-2.4 | |
| 4 | 02-03 | M | Random walks (cont'd), Max Cut (mp4 (2021) ) | Vadhan §2.3.2-2.4 | |
| 5 | 02-05 | W | Enumeration, Nonuniformity, Nondeterminism (mp4 (2021) ) | Vadhan §3.1-3.3 | |
| 6 | 02-10 | M | Conditional Expectations, Pairwise Independence (mp4 (2021) ) | Vadhan §3.4-3.5 | |
| 02-11 | T | pset1 due. pset2 out (tex/pdf) | |||
| 7 | 02-12 | W | k-wise Independence, Averaging Samplers (mp4 (2021) ) | Vadhan §3.4-3.5 | |
| 8 | 02-17 | M | Measures of Expansion, Existence (mp4 (2021) ) | Vadhan §4.1 | |
| 02-19 | T | ||||
| 9 | 02-20 | W | Expander Mixing Lemma, Expander Walks (mp4 (2021) ) | Vadhan §4.2 | |
| 10 | 02-24 | M | Expander Walks, Explicit Constructions (mp4 (2021) ) | Vadhan §4.2-4.3 | |
| 02-25 | T | pset2 due. | |||
| 11 | 02-26 | W | Explicit Constructions, USTCONN in L (mp4 (2021) ) | Vadhan §4.3-4.4 | |
| 12 | 03-03 | M | List-Decodable Codes (mp4 (2021) ) | Vadhan §5 | |
| 03-04 | T | pset3 out (tex/pdf) | |||
| 13 | 03-05 | W | List-Decodeable Codes (mp4 (2021) ) | Vadhan §5 | |
| 14 | 03-10 | M | List-Decodable Codes (mp4 (2021) ) | Vadhan §5 | |
| 03-11 | T | ||||
| 15 | 03-12 | W | List-Decodeable Codes (mp4 (2021) ) | Vadhan §5 | |
| 16 | 03-24 | M | Randomness Extractors (mp4 (2021) ) | Vadhan §6 | |
| 17 | 03-26 | W | Randomness Extractors (mp4 (2021) ) | Vadhan §6 | |
| 18 | 03-31 | M | Randomness Extractors (mp4 (2021) ) | Vadhan §6 | |
| 19 | 04-01 | W | Converting to Block Sources; GUV Extractor (mp4 (2021) ) | Vadhan §Sec. 6.3.2-6.3.4 |