A Linear-Time n 0.4-Approximation for Longest Common Subsequence

We consider the classic problem of computing the Longest Common Subsequence(LCS) of two strings of length $n$. While a simple quadratic algorithm has beenknown for the problem for more than 40 years, no faster algorithm has beenfound despite an extensive effort. The lack of progress on the problem hasrecently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15]and Bringmann and K\"unnemann [FOCS'15] who proved that there is nosubquadratic algorithm unless the Strong Exponential Time Hypothesis fails.This has led the community to look for subquadratic approximation algorithmsfor the problem. Yet, unlike the edit distance problem for which a constant-factorapproximation in almost-linear time is known, very little progress has beenmade on LCS, making it a notoriously difficult problem also in the realm ofapproximation. For the general setting, only a naive$O(n^{\varepsilon/2})$-approximation algorithm with running time$\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin,Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a$O(n^{0.497956})$-approximation in expectation; improving upon the naive$O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with highprobability, for any $0 $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound ofHajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whoseapproximation scales with any subquadratic running time $O(n^{2-\varepsilon})$,improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$,and (3) instead of only in expectation, succeeds with high probability.