Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).

Arturs Backurs, Piotr Indyk

Browse the full STOC paper archive.