UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Optimal Adaptive Detection of Monotone Patterns

Ben-Eliezer, O; Letzter, S; Waingarten, E; (2021) Optimal Adaptive Detection of Monotone Patterns. (In press).

[img] Text
adaptive.pdf - Accepted version
Access restricted to UCL open access staff until 24 May 2021.

Download (607kB)

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: Article
Title: Optimal Adaptive Detection of Monotone Patterns
Publisher version: https://arxiv.org/abs/1911.01169
Language: English
Additional information: This version is the author accepted 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 > 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.ucl.ac.uk/id/eprint/10107289
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item