Factor Three Approximation for Edit Distance

We give randomized algorithms for $3$-approximate edit distance in $\tilde{\mathcal{O}}(N^{11\mathrm{/}6})$ time for unweighted edit distance and in $\tilde{\mathcal{O}}(N^{40\mathrm{/}21})$ time for arbitrary metric edit weights, where $N$ is the total input length. For non-metric costs, we prove an unconditional $\mathrm{\Omega }(N^2)$ oracle-query lower bound for every approximation factor depending only on $N$, even for symmetric weights or weights satisfying the triangle inequality (but not both). Under the Orthogonal Vectors Hypothesis, we show a similar result for constant-size alphabets. This holds even for symmetric weights over a size-$3$ alphabet or triangle-inequality weights over a size-$2$ alphabet. In contrast, for symmetric weights over a binary alphabet we show an $\tilde{\mathcal{O}}(N^{40\mathrm{/}21})$-time $3$-approximation algorithm.