COURSE MATERIAL

Bibliography

Piotr Indyk

• 1. Philippe Flajolet, G. Nigel Martin: Probabilistic Counting Algorithms for Data Base Applications. J. Comp. Sys. Sci. 31(2): 182-209 (1985).
• 2. Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. STOC 1996: 20-29.
• 3. Piotr Indyk: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53(3): 307-323 (2006).
• 4. Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan. Geometric Approximation via Coresets.
• 5. Piotr Indyk: Algorithms for dynamic geometric problems over data streams. STOC 2004: 373-380.

Sudipto Guha

• 6. Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan. Clustering Data Streams. FOCS 2000: 359-366.
• 7. Moses Charikar, Liadan O'Callaghan, Rina Panigrahy. Better streaming algorithms for clustering problems. STOC 2003: 30-39.
• 8. Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani. Incremental Clustering and Dynamic Information Retrieval. STOC 1997: 626-635.
• 9. Sudipto Guha, Andrew McGregor. Approximate quantiles and the order of the stream. PODS 2006: 273-279.
• 10. J. Ian Munro, Mike Paterson. Selection and Sorting with Limited Storage. FOCS. 1978: 253-258.

Ravi Kumar and T.S. Jayram

• 11. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comp. Sys. Sci. 68(4): 702-732 (2004).
• 12. Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar: Sampling algorithms: lower bounds and applications. STOC 2001: 266-275
• 13. Paul Beame, T. S. Jayram, Atri Rudra: Lower bounds for randomized read/write stream algorithms. STOC 2007: 689-698
• 14. T. S. Jayram, Ravi Kumar, D. Sivakumar: The One-Way Communication Complexity of Gap Hamming Distance. Manuscript: 3 pages.

Martin Strauss

• 15. Graham Cormode, S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1): 58-75 (2005).
• 16. Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss. Fast, small-space algorithms for approximate histogram maintenance. STOC 2002: 389-398.
• 17. Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin. One sketch for all: fast algorithms for compressed sensing. STOC 2007: 237-246.
• 18. Emmanuel Candes, Justin Romberg, Terence Tao. Stable Signal Recovery from Incomplete and Inaccurate Measurements. Comm. Pure Appl. Math. 59(8) (2006), 1207-1223.

Bibliography links in progress

Lecture slides

Piotr Indyk: Introduction. Norm/Count estimation.

Sudipto Guha: Metric data. Clustering. Graph data.

Piotr Indyk: Geometric data. Clustering. MST.

T.S. Jayram: Lower bound I

T.S. Jayram: Lower bounds II

Sudipto Guha: Random order streams.

Ravi Kumar: Lower bounds 1 + 2.

Martin Strauss: Heavy hitters. Wavelets and histograms.

Martin Strauss: Compressed sensing, LP-based decoding, & Combinatorial decoding.

Background material

From the following links you may acquaint your self with the subjects of the summer school. The links direct to seminars etc. in which the lecturers of this Summer School have been involved.

• IITK Data Streams Workshop

• Dagstuhl Workshop on Sublinear Algorithms

• S. Muthukrishnan, Data Streams: Algorithms and Applications