Finding Monotone Patterns in Sublinear Time
Omri Ben‐Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten · 2019
We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed k ϵ N and ε > 0, we show that the non-adaptive query complexity of finding a length-k monotone subsequence of f : [n] → R, assuming that f is ε-far from free of such subsequences, is Θ((log n)⌊log_2k⌋). Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made (log n)O(k2)non-adaptive queries; and the only lower bound known, of Ω(log n) queries for the case k = 2, followed from that on testing monotonicity due to Ergün, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).