Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Let $n$ denote the size of the array. Simple $O(nlog n)$ algorithms are known for this problem. What can a sublinear time algorithm achieve? We develop a polylogarithmic time randomized algorithm that for any constant $delta > 0$, given $f$ outputs an estimate of the LIS that, with high probability, is accurate to within an additive $delta n$. More precisely, the running time of the algorithm is $(log n)^c (1/delta)^{O(1/delta)}$ where the exponent $c$ is independent of $delta$. Previously, the best known polylogarithmic time algorithms could only achieve an additive $n/2$ approximation.

The LIS problem can be formulated as a dynamic program. Our overall approach seems very general, and might be applicable to approximating other dynamic programs.

Questions and Answers

You need to be logged in to be able to post here.