## 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 collrected 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.