Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with non-adaptive:
TR19-134 | 4th October 2019
Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten

Finding monotone patterns in sublinear time

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 $\varepsilon$-far ... more >>>

ISSN 1433-8092 | Imprint