Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
This work addresses fundamental string similarity problems in computer science, providing significant insights into fine-grained complexity and derandomization hardness, though it is incremental in building on prior complexity assumptions.
The paper tackles the problem of approximating Edit Distance and Longest Common Subsequence by developing randomized algorithms that achieve near-optimal approximations in quasi-strongly subquadratic time, specifically improving runtime by a quasi-polynomial factor over classical methods.
We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant $ε>0$, compute a $(1+ε)$-approximation for ED and a $(1-ε)$-approximation for LCS in time $n^2 / 2^{\log^{Ω(1)}(n)}$ for two strings of total length at most $n$. This running time improves upon the classical quadratic-time dynamic programming algorithms by a quasi-polynomial factor. Our results yield significant insights into fine-grained complexity: Firstly, for ED, prior work indicates that any exact algorithm cannot be improved beyond a few logarithmic factors without refuting established complexity assumptions [Abboud, Hansen, Vassilevska Williams, Williams, 2016]; our quasi-polynomial speed-up shows a separation the complexity of approximate ED from that of exact ED, even for approximation factor arbitrarily close to $1$. Secondly, for LCS, obtaining similar approximation-time tradeoffs via deterministic algorithms would imply breakthrough circuit lower bounds [Chen, Goldwasser, Lyu, Rothblum, Rubinstein, 2019]; our randomized algorithm demonstrates derandomization hardness for LCS approximation.