| # | Date | lecture topic | reading | pset | |
|---|---|---|---|---|---|
| 1 | 01-17 | T | Intro, Bipartite Matching (pdf, audio) | SY §1, Harvey, Kleinberg §1.0,1.1,5.0-5.2,5.5.0-5.5.1 | |
| 2 | 01-19 | R | Algebraic Circuits, Homogenization, Elimination of Divisions (pdf, mp4) | SY §1.1,2.2.0,2.5 | |
| 01-23 | M | pset1 (tex/pdf) | |||
| 01-24 | T | cancelled due to technical problems | |||
| 3 | 01-26 | R | Constructions of algebraic circuits (pdf, mp4) | wikipedia, Kaltofen pg 2-3, Forbes §B.2, Rao (pdf, pdf ) | |
| 4 | 01-31 | T | Depth Reduction (pdf, mp4) | SY §2.4, Saptharishi §5.3.0,5.3.1,5.3.3, Forbes Lemma 7.2.4, Raz-Shpilka Lemma 2, BCS ex 21.17(a), Koiran §4 | |
| 5 | 02-02 | R | Completeness for VP, VNP (pdf, mp4) | SY §1.2, Saptharishi §3.0 -3.3.2 | |
| 02-07 | T | cancelled | |||
| 6 | 02-09 | R | Strassen's algorithm (pdf, mp4) | Bläser §1,2 | |
| 7 | 02-14 | T | Non-scalar and bilinear complexity (pdf, mp4) | Bläser §4 | |
| 8 | 02-16 | R | Exponent of Matrix Multiplication; Tensor Rank (pdf, mp4) | Bläser §4,5 | pset2 (tex/pdf) |
| 03-06 | M | pset3 (tex/pdf) |