# Edit Distance in Near-Linear Time: it's a Constant Factor

arXiv: https://arxiv.org/abs/2005.07678 · HTML: https://mlsanity.com/paper/2005.07678/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2020.

## Built on by (most cited first, 2 of 2)

- [Edit Distance Robust Watermarks via Indexing Pseudorandom Codes](https://mlsanity.com/paper/2406.02633/) (2024)
- [Can LLMs Deceive CLIP? Benchmarking Adversarial Compositionality of Pre-trained Multimodal Representation via Text Updates](https://mlsanity.com/paper/2505.22943/) (2025)

## Abstract (arXiv)

We present an algorithm for approximating the edit distance between two strings of length n in time n1+varepsilon up to a constant factor, for any varepsilon>0. Our result completes a research direction set forth in the recent breakthrough paper [Chakraborty-Das-Goldenberg-Kouck`y-Saks, FOCS'18], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results of [Kouck`y-Saks, STOC'20] and [Brakensiek-Rubinstein, STOC'20] have shown near-linear time algorithms that obtain an additive approximation, near-linear in n (equivalently, constant-factor approximation when the edit distance value is close to n). In contrast, our algorithm obtains a constant-factor approximation in near-linear time for any input strings. In contrast to prior algorithms, which are mostly recursing over smaller substrings, our algorithm gradually smoothes out the local contribution to the edit distance over progressively larger substrings. To accomplish this, we iteratively construct a distance oracle data structure for the metric of edit distance on all substrings of input strings, of length nivarepsilon for i=0,1,ldots,1/varepsilon. The distance oracle approximates the edit distance over these substrings in a certain average sense, just enough to estimate the overall edit distance.