This page contains links to papers that we covered and papers that are related to things we covered.

Jan 27: Simple Examples

Example 1: Testing monotonicity

Example 2: Approximate counting

Feb 3: Streaming Moments F_k

k=2: Alon, Matias, and Szegedy
k∊(0,2]: Indyk
Notes on Nisan's PRG: [Part 1] [Part 2]

Feb 10: Estimating the Number of Distinct Elements. Lower Bounds via Communication Complexity.

Estimating number of distinct elements:

See Section 3 of this lecture note
Optimal algorithm: Kane, Nelson, and Woodruff

Lower bounds via communication complexity:

See for instance this lecture note

Feb 17: Streaming Algorithms for the Longest Increasing Subsequence Length and the Median.

Longest Increasing Subsequence

Deterministic sqrt(n) algorithm: Gopalan, Jayram, Krauthgamer, and Kumar
Lower bound: Gál and Gopalan, Ergun and Jowhari
Very nice open question: Is there a randomized algorithm that uses o(sqrt(n)) space?

Median

O(log log n) passes for random order streams with polylog space: Guha and McGregor
(The paper also shows that Ω(log n / log log n) passes are required for adversarial order streams and polylog space.)
Ω(log log n) passes are needed for random order streams and polylog space: Chakrabarti, Jayram, and Pătraşcu
The shifting sands algorithm: McGregor and Valiant

Feb 24: Heavy hitters and the Count-Min Sketch

Finding a small set containing all frequent elements: Misra, Gries (1982), Demaine, López-Ortiz, and Munro (2002)
Count-Min Sketch: Cormode and Muthukrishan
A webpage dedicated to the Count-Min Sketch

Mar 2: Distributed Functional Monitoring

Paper that initated this line of research: Cormode, Muthukrishnan, and Yi
Interesting paper from the upcoming STOC: Woodruff and Zhang

Mar 9: Estimating the F_k Moment for k>2

Streaming Algorithms via Precision Sampling

Mar 23 & 30: Distribution Testing

Apr 6: Sublinear-Time Algorithms for Diameter and Minimum Spanning Tree Weight