## Final Project Suggestions

One of your options for a final project is to present a research paper in data streaming/sketching not already covered in the lectures. If you choose this route, you must do**both**of the following things.

- Write a review of the paper, summarizing its key results and contributions and commenting on its significance. Don't reproduce definitions, theorems, or proofs from the paper; summarize and paraphrase. Be critical, as appropriate. Imagine that a journal editor will use your review to decide whether or not to accept the paper to a prestigious journal. This entire review should be at most two pages long.
- Give a 25-minute slide-based talk (over Zoom) on the paper. Your target audience is the rest of the class. If needed, the talk should simplify the paper's ideas down to make it generally understandable to the class. Don't simplify so much that you fail to convey technical depth. A good talk will contain at least one significant proof from the paper (perhaps in outline form). Take turns being the speaker.

**The paper assignment is final only after you receive a confirmation statement from me**: first come, first served.

- Błasiok.
*Optimal streaming and tracking distinct elements with high probability*. - Cormode, Dark, Konrad.
*Independent Sets in Vertex-Arrival Streams*. - Esfandiari, Hajiaghayi, Liaghat, Monemizadeh, Onak.
*Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond*. - Hershberger, Suri.
*Adaptive sampling for geometric problems over data streams*. - Jayaram, Woodruff.
*Perfect Lp Sampling in a Data Stream*. - Magniez, Mathieu, Nayak.
*Recognizing Well-Parenthesized Expressions in the Streaming Model*. - Das Sarma, Gollapudi, Panigrahy.
*Estimating PageRank on Graph Streams*. - Paz, Schwartzman.
*A (2+ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model*.