Course reading

Here is a small list of papers for course reading. If you want to read any other paper of your choice, you are welcome to do so.

1. Faster streaming algorithms for graph spanners - Baswana. - Prahladha
2. Simpler algorithm for estimating frequency moments of data streams. - Bhuvanagiri, Ganguly, Kesh, Saha.
3. Graph sparsification in the semi-streaming model - Ahn, Guha. - Keshav
4. Efficient sketches for earth-mover distance, with applications - Andoni, Ba, Indyk, Woodruff.
5. A near-optimal algorithm for computing the entropy of a stream - Chakrabarty, Cormode, McGregor.
6. Distribution Testing Lower Bounds via Reductions from Communication Complexity - Blais, Canonne, Gur.
7. Approximating the Minimum Spanning Tree Weight in Sublinear Time - Chazelle, Rubinfeld, Trevisan. - Arnhav
8. Provable and practical approximations for the degree distribution using sublinear graph samples - Eden, Jain, Pinar, Ron, Seshadhri. - Karthikeyan
9. Local graph partitions for approximation and testing - Hassidim, Kelner, Nguyen, Onak.
10. Tight Lower Bounds for the Distinct Elements Problem - Indyk, Woodruff - Alan