Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ONE-SIDED TESTING:
Reports tagged with one-sided testing:
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