Optimal Adaptive Detection of Monotone Patterns

Abstract

We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed $2\le k\in \mathbb{N}$ and $\epsilon >0$, consider the problem of finding a length-$k$ increasing subsequence in an array $f:[n]\to \mathbb{R}$, provided that $f$ is $\epsilon$-far from free of such subsequences. Recently, it was shown that the non-adaptive query complexity of the above task is $\Theta ((\log n{)}^{\lfloor {\log }_{2}k\rfloor })$. In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes $O(\log n)$ queries. This is optimal, matching the classical $\Omega (\log n)$ adaptive lower bound by Fischer [2004] for monotonicity testing (which corresponds to the case $k=2$), and implying in particular that the query complexity of testing whether the longest increasing subsequence (LIS) has constant length is $\Theta (\log n)$.