2019/11/04 by Ben-Eliezer, Omri, Letzter, Shoham, Waingarten, Erik
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.01169
We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed 2 ≤ k ∈ ℕ and ε > 0, consider the problem of finding a length-k increasing subsequence in an array f \colon [n] → ℝ, 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 Θ((log n)\lfloor log2 k \rfloor). In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes O(log n) queries. This is optimal, matching the classical Ω(log n) 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 Θ(log n).