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
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
3. F. Ergün and H. Jowhari, On distance to monotonicity and longest increasing subsequence of a data stream, SODA 2008. 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
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

Source

Imported from Sublinear.info, Problem 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.