Today, we consider estimating the median of a set of values given a single pass over a stream formed by randomly permuting the set. Seems like a pretty simple problem, right?
It’s known that we can find an -approximate median, i.e., an element with rank , in polylog space, with probability 9/10 where the probability is taken over both the coin flips of the algorithm and the random permutation. However, the best known lower bound states that finding a -approximate median requires space [Guha, McGregor]. If this bound is optimal, it would be possible to find a -approximate median in polylogarithmic space. Does there exist such an algorithm or can the lower bound be improved?
Background. The exact median can be found in space [Munro, Paterson]. It seems reasonable to conjecture that space is necessary and sufficient to find a -approximate median.
(Disclaimer: I’ve suppressed some poly-log and poly-constant terms above. And, actually, you can shave-off one of the terms I didn’t mention in the lower bound if you consider some public random bits in the argument.)