The project for the course is a short slide presentations (up to 15 minutes) on the main high level ideas in some paper or on some open problem or topic in sublinear algorithms and what is known about it. These can also be descriptions of an application/implementation of the topics or ideas in the general area of the course to work you are doing or have done. Any of the open problems or topics on the website would be a good choice. Some sample topics and associated papers are listed below.

  1. Estimating Entropy in Streams:

    Amit Chakrabarti Graham Cormode and Andrew McGregor A Near-Optimal Algorithm for Estimating the Entropy of a Stream ACM Transactions on Algorithms, Vol. 6, No. 3, Article 51, June 2010.

  2. Problem 44: Distance to monotonicity and LIS:

    Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. Estimating the sortedness of a data stream. In ACM-SIAM Symposium on Discrete Algorithms, pages 318-327, 2007

    Amit Chakrabarti. A note on randomized streaming space bounds for the longest increasing subsequence problem. Electronic Colloquium on Computational Complexity (ECCC), 10(10), 2010.

  3. Semi-streaming algorithms for graph problems:

    Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207-216, 2005.

  4. Cascaded norm estimation: e.g. what is the variance of the degrees in a graph stream?

    T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded norms. In IEEE Symposium on Foundations of Computer Science, 2009.

  5. Estimating the median in random-order streams:

    Andrew McGregor and Paul Valiant. The Shifting Sands Algorithm. Proc. 23rd Symposium on Discrete Algorithms (SODA), 2012. (Makrand will present)

  6. Edit distance:

    Incremental String comparison, S. Landau, E. Meyers, J. Schmidt. SIAM J. Comput vol 27, no. 2, April 1998.

    Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

  7. Edit Distance for permutations/non-repeating strings (Ulam metric)

    Hossein Jowhari. Efficient Communication Protocols for Deciding Edit Distance In ESA, 2012. (Alex will present)

    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. Approximating edit distance efficiently. In FOCS, pages 550{559, 2004.

  8. Fp estimation for 1<p<2:

    Piotr Indyk, Stable Distributions, Pseudorandom Generators, Embeddings, and Data Stream Computation. J. ACM, 2006.

  9. Better space for quantile summaries (approximate rank):

    Greenwald, Khanna. Space-Efficient Online Computation of Quantile Summaries.

  10. Optimal F0 estimation:

    Kane, Daniel M., Jelani Nelson, and David P. Woodruff. "An optimal algorithm for the distinct elements problem." Proc. ACM Symposium on Principles of Database Systems. 2010. (Erik will present)

  11. Sundaram, Turmukhametova, Satish, Mostak, Indyk, Madden, Dubey. Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing (Ajay will present)