Finding Monotone Patterns in Sublinear Time
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).
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
41
References
0
Citations
NaN
KQI