Problem 44: Approximating LIS Length in the Streaming Model

Suggested by	Amit Chakrabarti
Source	Bertinoro 2011
Short link	https://sublinear.info/44

The goal of LIS is to compute a $2$-approximation of the length of the longest increasing subsequence in a given stream of elements.

Question: What is the randomized streaming space complexity of LIS, for one pass or possibly a constant number of passes?

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.