Instructor	Huacheng Yu
Lectures	Tuesday/Thursday 3:00-4:20pm
Location	Robertson Hall 005
Office hours	Thursday 4:30-5:30pm, CS building 310

This course focuses on algorithms that compress data in such a way that certain pre-specified queries can be answered. The course covers the mathematical models, algorithm design and analysis, as well as provable limitations of efficient algorithms in those models. The topics covered in the course include counting in streams, linear sketches, graph streaming, dimensionality reduction, etc.

Workload

• One problem set due in late Nov. Problems will be added throughout the semester. You are expected to work on any ~ ½ of the problems.
• One presentation. You will give one ~ 25 min presentation. There are two options for the topic: you can either present one research paper on streaming / sketching algorithms, or present a survey on applications or connections of streaming / sketching algorithms to an area of your interest.

Problem set: here

List of papers for presentation: here

(Tentative) Schedule

Lecture #	Date	Topic
	Th 9/2	no lecture
1	T 9/7	introduction, logistics, approximate counting
2	Th 9/9	distinct elements
3	T 9/14	distinct elements II
4	Th 9/16	lower bounds for distinct elements
5	T 9/21	quantile estimation
6	Th 9/23	linear sketches, turnstile streaming, point query, CountMin sketch
7	T 9/28	heavy hitters lower bound, Count sketch
8	Th 9/30	AMS sketch, ℓp norm estimation
9	T 10/5	sparse recovery, support finding
10	Th 10/7	ℓp sampler
11	T 10/12	ℓp sampler wrap-up, AGM sketch
12	Th 10/14	more graph streaming
	T 10/19	fall break
	Th 10/21	fall break
13	T 10/26	Johnson-Lindenstrauss transform, fast JL
14	Th 10/28	sparse JL
15	T 11/2	JL lower bound
16	Th 11/4	approx matrix mult
17	T 11/9	subspace embedding
18	Th 11/11	final presentations
19	T 11/16	final presentations
20	Th 11/18	final presentations
21	T 11/23	final presentations
	Th 11/25	thanksgiving break
22	T 11/30	final presentations
23	Th 12/2	open problem session