Finding monotone patterns in sublinear time

Abstract

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k\in \mathbb{N}$ and $\epsilon >0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f:[n]\to \mathbb{R}$, assuming that $f$ is $\epsilon$-far from free of such subsequences, is $\Theta ((\log n{)}^{\lfloor {\log }_{2}k\rfloor })$. Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made $(\log n{)}^{O(k^2)}$ non-adaptive queries; and the only lower bound known, of $\Omega (\log n)$ queries for the case $k=2$, followed from that on testing monotonicity due to Ergün, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).

References in corpus (1)

• Faster and simpler algorithms for finding large patterns in permutations

Cited by in corpus (2)

• A Simple Sublinear Algorithm for Gap Edit Distance
• Does Preprocessing help in Fast Sequence Comparisons?