Finding monotone patterns in sublinear time

by Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, and Erik Waingarten

Oded's comments

In the past, some people collected mail stamps, others collected other items. Nowadays, it seems natural to collect ideas (or notions). Anyhow, I collect complexities that characterize the requirements for natural computational problems. So here is one to my collection....
(Indeed, hierarchy theorems are well known (also for property testing), but they don't refer to natural problems.)

The original 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 $\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 $\dd$-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 Ergun, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).

See ECCC TR19-134.

Back to list of Oded's choices.