Estimating the longest increasing sequence in polylogarithmic time

Understand

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem.

• Let $n$ denote the size of the array.
• Simple $O(n\log n)$ algorithms are known for this problem.
• We develop a polylogarithmic time randomized algorithm that for any constant $\delta > 0$, estimates the length of the LIS of an array to within an additive error of $\delta n$.