Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

The problem of computing the exact edit distance can be solved using a classical dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) show that one can compute an approximation to the edit distance within approximation factor polylog(n) in nearly linear time. Recently, Abboud and Backurs (ITCS'17) showed that under reasonable hardness assumptions the edit distance cannot be approximated within (1+o(1))-factor in truly sub-quadratic time. This raises the question whether edit distance can be approximated within constant factor in truly sub-quadratic time.

In the talk I will present our work where we affirmatively answer this question by providing an algorithm whose running time is bounded by
tilde-O(n^{2-2/7}) that approximates the edit distance up-to constant factor. Our approximation algorithm is based on a new yet simple paradigm.