Amit Chakrabarti

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 >>>