# Approximating the longest increasing subsequence in a stream

Patience sorting finds the longest increasing subsequence of a stream exactly, but it needs linear space, and exact computation cannot do better. Deterministic one-pass algorithms approximate its length within any constant factor in about $\sqrt n$ space, which is optimal for them; whether randomization can do better is open.

## Problem

A stream $\sigma = (\sigma_1, \dots, \sigma_n)$ of integers from $\{1, \dots, m\}$ arrives one element at a time. An increasing subsequence is a set of positions $i_1 < \dots < i_k$ with $\sigma_{i_1} < \dots < \sigma_{i_k}$, and $\mathrm{lis}(\sigma)$ is the largest such $k$. A streaming algorithm makes one pass (or a constant number of passes) over $\sigma$ using limited memory and outputs $\ell$. It is a $c$-approximation if $\mathrm{lis}(\sigma) \le \ell \le c \cdot \mathrm{lis}(\sigma)$, with probability at least $2/3$ for a randomized algorithm.

**Question.** What is the space complexity of randomized streaming algorithms, with one or a constant number of passes, that approximate $\mathrm{lis}(\sigma)$ within a constant factor, say $2$? In particular, is there one that uses $o(\sqrt n)$ space, or is $\Omega(\sqrt n)$ space, or at least $n^{\Omega(1)}$, necessary?

## Background

The longest increasing subsequence is a basic measure of how sorted a sequence is: $n - \mathrm{lis}(\sigma)$ is the number of elements that must be moved to sort it. Gopalan, Jayram, Krauthgamer and Kumar gave the first sublinear-space streaming algorithms for it and raised the question of whether $\sqrt n$ space is necessary [1]. Amit Chakrabarti posed the randomized version at the 2011 Bertinoro Workshop on Sublinear Algorithms, and Andoni, Nosatzki, Sinha and Stein (2022) call settling the streaming complexity a major open problem [5].

## What is known

- **Exact computation** needs $\Omega(n)$ space even for randomized algorithms (Gopalan, Jayram, Krauthgamer and Kumar; Sun and Woodruff; 2007) [1], so patience sorting is optimal.
- **Deterministic upper bound.** A one-pass deterministic algorithm achieves a $(1+\varepsilon)$-approximation in $O(\sqrt{n/\varepsilon}\,\log m)$ space [1].
- **Deterministic lower bound.** Any deterministic algorithm with a constant number of passes that approximates $\mathrm{lis}$ within a constant factor needs $\Omega(\sqrt n)$ space (Gál and Gopalan [2]; independently, for factors close to 1, Ergün and Jowhari [3]).
- **Randomized.** The communication problems behind these lower bounds have cheap randomized protocols, so the same method cannot give randomized lower bounds (Chakrabarti) [4]. No randomized algorithm with $o(\sqrt n)$ space is known [5].
- **The complementary quantity**, the distance from monotonicity $n - \mathrm{lis}(\sigma)$, is much easier: it can be approximated within $1+\varepsilon$ in polylogarithmic space, as surveyed in [5].

## What would count as progress

- A randomized algorithm with $o(\sqrt n)$ space, ideally polylogarithmic, that approximates $\mathrm{lis}$ within a constant factor on every stream, with a proof. Candidate algorithms can be stress-tested on adversarial streams against patience sorting.
- A lower bound of $n^{\Omega(1)}$ space for randomized constant-factor approximation, for example through a new communication problem that resists randomized protocols.
- Settling intermediate versions, such as randomized algorithms with larger constant approximation factors or with a few passes.

## References

1. P. Gopalan, T. S. Jayram, R. Krauthgamer and R. Kumar, Estimating the sortedness of a data stream, SODA 2007, 318–327. [PDF](https://www.wisdom.weizmann.ac.il/~robi/papers/GJKK-stream-SODA07.pdf)
2. A. Gál and P. Gopalan, Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence, *SIAM J. Comput.* 39(8) (2010), 3463–3479. [doi:10.1137/090770801](https://doi.org/10.1137/090770801)
3. F. Ergün and H. Jowhari, On distance to monotonicity and longest increasing subsequence of a data stream, SODA 2008. [PDF](https://homes.luddy.indiana.edu/fergun/PUBLICATIONS/lis.pdf)
4. A. Chakrabarti, A note on randomized streaming space bounds for the longest increasing subsequence problem, *Inform. Process. Lett.* 112(7) (2012), 261–263. [doi:10.1016/j.ipl.2011.12.008](https://doi.org/10.1016/j.ipl.2011.12.008)
5. A. Andoni, N. S. Nosatzki, S. Sinha and C. Stein, Estimating the longest increasing subsequence in nearly optimal time, FOCS 2022. [arXiv:2112.05106](https://arxiv.org/abs/2112.05106)

## Source

Imported from [Sublinear.info, Problem 44](https://sublinear.info/44), curated by Sublinear.info editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.