1
$\begingroup$

Can we compute the edit distance between two strings of length $n$ in strongly sub-quadratic time, i.e., in time $O(n^{2−\epsilon})$ for some $\epsilon>0$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.