Instructor  Huacheng Yu 
Lectures  Tuesday/Thursday 3:004:20pm 
Location  Robertson Hall 005 
Office hours  Thursday 4:305:30pm, CS building 310 
This course focuses on algorithms that compress data in such a way that certain prespecified 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 wrapup, AGM sketch 
12  Th 10/14  more graph streaming 
 T 10/19  fall break 
 Th 10/21  fall break 
13  T 10/26  JohnsonLindenstrauss 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 