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.)
Recent Comments