Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time

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.