Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael Saks

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time Õ(n2-2/7) that approximates the edit distance within a constant factor.

Original languageEnglish (US)
Article number36
JournalJournal of the ACM
Issue number6
StatePublished - Nov 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Edit distance
  • approximation algorithm
  • randomized algorithm
  • sub-quadratic time algorithm


Dive into the research topics of 'Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time'. Together they form a unique fingerprint.

Cite this