Parallel Longest Increasing Subsequence and van Emde Boas Trees
Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, Zijin Wan · 2023
This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let n be the input size and k be the LIS length of the input. Sequentially, LIS is a simple problem that can be solved using dynamic programming (DP) in O(n log n) work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal O(n log n) work and non-trivial parallelism (i.e., Õ(k) or o(n) span).