Ben-Eliezer, O;
Letzter, S;
Waingarten, E;
(2021)
Optimal Adaptive Detection of Monotone Patterns.
arXiv.org: Ithaca (NY), USA.
Preview |
Text
adaptive.pdf - Accepted Version Download (607kB) | Preview |
Abstract
We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed 2≤k∈N and ε>0, consider the problem of finding a length-k increasing subsequence in an array f:[n]→R, provided that f is ε-far from free of such subsequences. Recently, it was shown that the non-adaptive query complexity of the above task is Θ((logn)⌊log2k⌋). In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes O(logn) queries. This is optimal, matching the classical Ω(logn) adaptive lower bound by Fischer [2004] for monotonicity testing (which corresponds to the case k=2), and implying in particular that the query complexity of testing whether the longest increasing subsequence (LIS) has constant length is Θ(logn).
| Type: | Working / discussion paper |
|---|---|
| Title: | Optimal Adaptive Detection of Monotone Patterns |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://doi.org/10.48550/arXiv.1911.01169 |
| Language: | English |
| Additional information: | This version is the author manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10107289 |
Archive Staff Only
 |
View Item |
