English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate adaptive sublinear algorithms for detecting monotone patternsin an array. Given fixed $2 \leq k \in \mathbb{N}$ and $\varepsilon > 0$,consider the problem of finding a length-$k$ increasing subsequence in an array$f \colon [n] \to \mathbb{R}$, provided that $f$ is $\varepsilon$-far from freeof such subsequences. Recently, it was shown that the non-adaptive querycomplexity of the above task is $\Theta((\log n)^{\lfloor \log_2 k \rfloor})$.In this work, we break the non-adaptive lower bound, presenting an adaptivealgorithm for this problem which makes $O(\log n)$ queries. This is optimal,matching the classical $\Omega(\log n)$ adaptive lower bound by Fischer [2004]for monotonicity testing (which corresponds to the case $k=2$), and implying inparticular that the query complexity of testing whether the longest increasingsubsequence (LIS) has constant length is $\Theta(\log n)$.

Optimal Adaptive Detection of Monotone Patterns