Constant-factor approximation of near-linear edit distance in near-linear time

We show that the edit distance between two strings of length n can be computed within a factor of f ( ) in n 1+ time as long as the edit distance is at least n 1-δ for some δ( ) > 0. * We thank Clément Canonne, Ray Li, Seri Khoury, Barna Saha, and anonymous reviewers for valuable suggestions for the manuscript. † Stanford University, supported by the NSF GRFP ‡ Stanford University 1 More precisely, LCS is equivalent to edit distance computation without substitutions since EDno-subs(A, B) = 2n -LCS(A, B). For our purposes the question of whether we allow substitutions in the definition of edit distance is irrelevant since the two definitions are equivalent up to a multiplicative factor of 2.