18
$\begingroup$

In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array. In particular they focus on the following model:

the input is read from left to right for a number P of times.

It is shown that $O(n^{\frac{1}{2P}})$ memory cells are sufficient, but the corresponding lower bound is only known for P=1. I haven't seen any result for P>1. Is anyone aware of such lower bounds?

Notice that the main difficulty here is that at the second pass the input is not randomly ordered anymore.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

Try this paper by Chan in a recent SODA: http://portal.acm.org/citation.cfm?id=1721842&dl=ACM .

A quick Google search also found the following paper that looks possibly relevant, but I haven't read it: http://portal.acm.org/citation.cfm?id=1374470 .

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, the second paper seems to give a partial answer to my question. Such answer is not present in earlier papers I was aware of. $\endgroup$
    – MassimoLauria
    Oct 21, 2010 at 19:10
18
$\begingroup$

The first paper to prove bounds for more than 1 pass was my paper with Jayram and Amit from SODA'08. Then there is the paper that Warren mentioned, which improves the bounds by a cleaner proof.

In short, we understand the dependence if you allow constants in front of the number of passes. Of course, these constants are in the exponent, so you can ask for a precise understanding. My main complaint is that the model of multipass streaming is not all that well motivated.

The more intriguing question is whether we can prove a branching program lower bound. Can it be that even for a bounded space algorithm that can access memory as it pleases, the best strategy is to just do multipass streaming?

The answer appears to be affirmative, and we have some partial progress towards proving it.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ I think multipass streaming is a natural model in following kind of experiments: You use randomised sampling to do statistical testing (e.g., permutation testing). You run billions of experiments; each experiment gets random numbers from a PRNG and produces some output values. Then you want to compute medians, histograms, etc., of these values. You don't have efficient random access to your stream of outputs and you don't have memory to store everything. However, you can re-play the stream; just reset your PRNG with the same seed and re-run your algorithm. $\endgroup$
    – Jukka Suomela
    Oct 22, 2010 at 10:34
  • 2
    $\begingroup$ We can all agree that the best is having upper bounds in the multipass streaming model and matching lower bounds in for some relevant family of branching programs. $\endgroup$
    – MassimoLauria
    Oct 22, 2010 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.