The lecture notes will be generated continuously as the course progresses.

Lecture Schedule

Lec# Date Topic Reading
1 Wednesday, 8/26/20 logistics, course topics, approximate counting (Morris Counter) vid § 2.1
2 Monday, 8/31/20 distinct elements, k-wise independence vid § 2.2.1-2.2.2
3 Wednesday, 9/2/20 geometric sampling vid § 2.2.3
Monday, 9/7/20 NO CLASS
4 Wednesday, 9/9/20 quantiles vid § 2.3
5 Monday, 9/14/20 lower bounds via compression arguments vid § 3.1
6 Wednesday, 9/16/20 lower bounds via communication complexity vid § 3.2
7 Monday, 9/21/20 linear sketching, turnstile streaming, heavy hitters vid
8 Wednesday, 9/23/20
9 Monday, 9/28/20
10 Wednesday, 9/30/20
11 Monday, 10/5/20 Guest Lecture: Ilya Razenshteyn
12 Wednesday, 10/7/20
13 Monday, 10/12/20
14 Wednesday, 10/14/20
15 Monday, 10/19/20
16 Wednesday, 10/21/20
17 Monday, 10/26/20
18 Wednesday, 10/28/20
19 Monday, 11/2/20
20 Wednesday, 11/4/20
21 Monday, 11/9/20
Wednesday, 11/11/20 NO CLASS
22 Monday, 11/16/20
23 Wednesday, 11/18/20
24 Monday, 11/23/20
Wednesday, 11/25/20 NO CLASS
25 Monday, 11/30/20
Wednesday, 12/2/20 Project presentations
Wednesday, 12/7/20 Project presentations
Wednesday, 12/9/20 Project presentations