Optimal Adaptive Detection of Monotone Patterns

MaRDI QIDQ6328468zbMATH OpenFDO

Authors Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten

Publication date 4 November 2019

Abstract: We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed $2leqkinmathbbN$ and $varepsilon>0$, consider the problem of finding a length-$k$ increasing subsequence in an array $fcolon[n]omathbbR$, provided that $f$ is $varepsilon$-far from free of such subsequences. Recently, it was shown that the non-adaptive query complexity of the above task is $Theta((logn{)}^{lfloorlo{g}_{2}kfloor})$. In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes $O(logn)$ queries. This is optimal, matching the classical $Omega(logn)$ 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(logn)$.

This page was built for publication: Optimal Adaptive Detection of Monotone Patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328468)