- Aug. 30, 2012: Webpage created

See below. Note: time slots can be different for different lectures.

Lecture | Date and Venue | Content | Literature |
---|---|---|---|

1 | Sep. 3, 1:30-3pm, at 3405 | Introduction to linear sketch and the streaming model, distinct elements | [Mut05], [Ind07] Lecture 1 |

2 | Sep. 4, 1:30-3pm, at 3405 | L2 norm, stable distribution, Lp (p>2) norms | [Ind07] Lecture 3, [Ind06] |

3 | Sep. 5, 1:30-3pm, at 3405 | Heavy hitters, L1/L2 point query | [Ind07] Lecture 4 |

4 | Sep. 10, 1:30-3pm, at 3405 | Introduction to compressive sensing, for each L1/L1, for all L1/L2 | [GI10], [Ind07] Lecture 5-6 |

5 | Sep. 12, 4:30-6pm, at 3301A | For all L1/L2 (cont.) | [Ind07] Lecture 5-6, [Rice] Chapter 4 |

6* | Sep. 17, 1:30-3pm, at 3405 | Introduction to communication complexity, sparse recovery lower bounds | [JW11], [DIPW10] |

7 | L0 sampling, graph algorithms | [AGM12a], [AGM12b] |

Still under construction. A temporary draft here

- [Ind07] Sketching, Streaming and Sub-linear Space Algorithms by P. Indyk.
- [Rice] An Introduction to Compressive Sensing by R. Baraniuk, M. A. Davenport, M. F. Duarte, C. Hegde.
- [GI10] Sparse Recovery Using Sparse Matrices" by A. Gilbert and P. Indyk.
- [JW11] Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Low Error by T. S. Jayram and D. P. Woodruff.
- [DIPW10] Lower Bounds for Sparse Recovery by K. Ba, P. Indyk, E. Price and D. P. Woodruff.
- [AGM12a] Analyzing Graph Structure via Linear Measurements by K. Ahn, S. Guha and A. Mcgregor.
- [AGM12b] Graph Sketches: Sparsfiers, Spanners, and Subgraphs by by K. Ahn, S. Guha and A. Mcgregor.
- [Mut05] Data Streams: Algorithms and Applications by S. Muthukrishnan.
- [Ind06] Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation by P. Indyk