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.
Below is an evolving list of papers that I think are suitable for this final project. You are welcome
to pick a paper not from my list, but I must approve it. You must write to me (post publicly on
Piazza) naming all members of your project team (up to three) and the details of the paper you have
chosen.
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.
