# Problem 44: Approximating LIS Length in the Streaming Model

The goal of LIS is to compute a $2$-approximation of the length of the longest increasing subsequence in a given stream of elements.
Background: Gopalan et al. [GopalanJKK-07] gave an $O(n^{1/2} \operatorname{polylog}(n))$-space deterministic streaming algorithm, using one pass, that achieves $c$-approximation for any fixed $c>0$. For deterministic algorithms [GalG-07,ErgunJ-08] showed an $\Omega(n^{1/2})$ space lower bound, for a constant number of passes. The latter arguments proceed by proving a lower bound for related communication complexity problems. However, it is known that the randomized communication complexity of those problem is $O(\log n)$ [Chakrabarti-10] so a different approach is needed.