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