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.


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