2019/10/03 by Omri Ben‐Eliezer, Clément L. Canonne, Ben-Eliezer, Omri +5
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1910.01749
openalex publication_date 2019/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed k ∈ ℕ and ε > 0, we show that the non-adaptive query complexity of finding a length-k monotone subsequence of f \colon [n] → ℝ, assuming that f is ε-far from free of such subsequences, is Θ((log n)\lfloor log2 k \rfloor). 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).