The deterministic space complexity of approximating the length of the longest increasing subsequence of
a stream of N integers is known to be \widetilde{\Theta}(\sqrt N). However, the randomized
complexity is wide open. We show that the technique used in earlier work to establish the \Omega(\sqrt N) deterministic lower bound fails ... more >>>