Storage requirements for median selection (two passes algorithms) 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.
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.