Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LONGEST INCREASING SUBSEQUENCE:
Reports tagged with longest increasing subsequence:
TR10-100 | 25th June 2010
Amit Chakrabarti

#### A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem

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

ISSN 1433-8092 | Imprint