Constant factor approximations to edit distance on far input pairs in nearly linear time

For any T ≥ 1, there are constants R = R(T ) ≥ 1 and ζ = ζ(T ) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n 1+ 1 T ) and outputs an upper bound U on the edit distance of d edit (x, y) that with high probability, satisfies U ≤ R(d edit (x, y) + n 1-ζ ). In particular, on any input with d edit (x, y) ≥ n 1-ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein [14].