The authors of the paper note (though this MIT News summary omits) that there is a well-known algorithm for edit distance that runs is subquadratic time. In fac

The authors of the paper note (though this MIT News summary omits) that there is a well-known algorithm for edit distance that runs is subquadratic time. In fact, it runs in O(n^2/log^2 n) on a word RAM. It uses a method sometimes called "Four Russians" or "shaving a log". Of course, this does not invalidate the results; I mention it only to dispel the notion that a reader may get from this MIT News summary that there is no subquadratic algorithm likely to be found. It's also interesting reading; just Google for "edit distance" and "Four Russians" and you'll find many summaries.