Efficiently Approximating Edit Distance Between Pseudorandom Strings

William Kuszmaul

We present an algorithm for approximating the edit distance $\mathrm{ed}(x,y)$ between two strings $x$ and $y$ in time parameterized by the degree to which one of the string…