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

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2014.

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

- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [CostBench: Evaluating Multi-Turn Cost-Optimal Planning and Adaptation in Dynamic Environments for LLM Tool-Use Agents](https://mlsanity.com/paper/2511.02734/) (2025)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [Limits of Transformer Language Models on Learning to Compose Algorithms](https://mlsanity.com/paper/2402.05785/) (2024)
- [string2string: A Modern Python Library for String-to-String Algorithms](https://mlsanity.com/paper/2304.14395/) (2023)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025)
- [LLM-Guided Search for Deletion-Correcting Codes](https://mlsanity.com/paper/2504.00613/) (2025)
- [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025)
- [Deep Squared Euclidean Approximation to the Levenshtein Distance for DNA Storage](https://mlsanity.com/paper/2207.04684/) (2022)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel](https://mlsanity.com/paper/2312.12717/) (2023)
- [FlexiTerm: A more efficient implementation of flexible multi-word term recognition](https://mlsanity.com/paper/2110.06981/) (2021)
- [On the k-Hamming and k-Edit Distances](https://mlsanity.com/paper/2306.09144/) (2023)
- [On the Computational Hardness of Transformers](https://mlsanity.com/paper/2603.11332/) (2026)

## Abstract (arXiv)

The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming. Unfortunately, all known algorithms for this problem run in nearly quadratic time. In this paper we provide evidence that the near-quadratic running time bounds known for the problem of computing edit distance might be tight. Specifically, we show that, if the edit distance can be computed in time O(n2-δ) for some constant δ>0, then the satisfiability of conjunctive normal form formulas with N variables and M clauses can be solved in time MO(1) 2(1-ε)N for a constant ε>0. The latter result would violate the Strong Exponential Time Hypothesis, which postulates that such algorithms do not exist.