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 sublinear.info website would be a good choice. Some sample topics and associated papers are listed below.
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.
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.
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.
T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded norms. In IEEE Symposium on Foundations of Computer Science, 2009.
Andrew McGregor and Paul Valiant. The Shifting Sands Algorithm. Proc. 23rd Symposium on Discrete Algorithms (SODA), 2012. (Makrand will present)
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
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.
Piotr Indyk, Stable Distributions, Pseudorandom Generators, Embeddings, and Data Stream Computation. J. ACM, 2006.
Greenwald, Khanna. Space-Efficient Online Computation of Quantile Summaries.
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)