209 citations · 414 across the 29 of their papers we have counts for
1 paper · 1 filter
Alexandr Andoni, Krzysztof Onak
We show how to compute the edit distance between two strings of length n up to a factor of 2^{Õ(sqrt(log n))} in n^(1+o(1)) time. This is the first sub-polynomial approximation alg…