Zhao Song

An $n^{8/5+o(1)}$-Time $\Omega(\lambda^3)$-Approximation for Longest Common Subsequence

Let $\lambda$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $\Omega(\lambda^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}...