On the monotonicity of a data stream (Q1677498)

In this paper the authors consider problems related to the sortedness of a data stream. In the first part of this work the problem of estimating the distance to monotonicity is investigated. Then the problem of approximating the length of the longest increasing subsequence of the input stream is discussed. Through the analysis of a multi-party communication game, bounds are given using the deterministic streaming algorithms that approximate the length of the longest increasing subsequence.