Minor remark: If the edit distance between two n-length strings is (relatively) small, it is possible to find it in subquadratic time. More precisely, if the edit distance is at most d, you can solve the problem in O(nd) time. The upper bound d does not have to be known in advance. The conditional lower bound you mentioned holds only for large values of edit distance.