ECCC-Report TR19-134https://eccc.weizmann.ac.il/report/2019/134Comments and Revisions published for TR19-134en-usFri, 04 Oct 2019 18:42:39 +0300
Paper TR19-134
| Finding monotone patterns in sublinear time |
Omri Ben-Eliezer,
Clement Canonne,
Shoham Letzter,
Erik Waingarten
https://eccc.weizmann.ac.il/report/2019/134We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in \mathbb{N}$ and $\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f \colon [n] \to \mathbb{R}$, assuming that $f$ is $\varepsilon$-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\"un, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).Fri, 04 Oct 2019 18:42:39 +0300https://eccc.weizmann.ac.il/report/2019/134