I like the choice of the topic. Quantile estimation is a fundamental
question in streaming algorithms and enables covering quite a number of
basic sketching techniques. In general, you managed to cover most of it, in
a pretty good style.
I wish though the presentation was a little bit less paper-centric and
more technique-centric. Yes, these two views are somewhat correlated, as
each paper was building on the previous one, but there was room for a more
broad and unified view. Also, by the time you got the the KLL result, the
style degraded pretty substantially and became powering through all the
technical details needed to make this work. It was hard to follow at this
point. I think covering less, while black boxing/suppressing some of the
parts, would be more valuable.
(Note: some of these points were already made in the feedback that you
received on your draft.)
Still, the first half was a pretty good read, with simple but helpful
figure. I think I learned something.
What worries me the most though are some of the off-hand
statements/"proofs" that you provide. In particular, the "proof" of
Omega(n) lower bound for exact median estimation, and the Omega(eps^-1)
lowerbound for eps-approximate quantile estimation. They make the pretty
fundamental fallacy of assuming that the hypothetical algorithm has to
"store" specific elements from the stream. This is not how lower bounds
work! The algorithm could, in principle, do various crazy things with the
elements it sees. E.g., take a hash of subset of elements and store them as
a single number. Does it mean then that we "stored" all these elements or
we did not? Similarly, statement that a given upper bound "does not seem
tight as it still grows with n" seems very puzzling and unsubstantiated.
(You have a more appropriate comment about this bound later on though.)
I am not sure what to think of these fallacies. I hope that what you meant
there is to just provide some general intuitions for the lower bounds, and
you actually understand the problem with treating them as formal arguments.
Also, the English could use improvement in some parts. In particular, some
of the word choices are a bit non-standard/awkward. (E.g., we say "black
box manner" instead of "opaque manner", instead of calling a problem
"expensive" we actually say that solving it requires a lot of space, etc.)
In any case though, as I said, I rather enjoyed the topic and the read.
So, good job!
Grade: B