# Almost-linear approximation of edit distance > Edit distance can be estimated to within any fixed accuracy in barely more than linear time. Plain-English explainer, Lean status and sources. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-121/ Last updated: 2026-10-11 **Edit distance can be estimated to within any fixed accuracy in barely more than linear time.** **Trust:** Formal proof listed · **Papers:** 1 · **First paper:** September 24, 2026 · **Field:** Theoretical computer science · **Entry:** 121 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. The edit distance between two strings counts the fewest one-symbol changes that turn one into the other. The classic exact method takes time that grows like the square of the length. This paper proves a random method can estimate it within a factor 1 + ε, for any fixed ε below 1. It succeeds with probability at least 2/3, and its expected running time is barely more than linear. The speed only applies to astronomically long strings, so it is a theoretical result. ## At a glance - **First step:** 1974 (Wagner and Fischer, quadratic table method) - **Significance:** Major. It pairs accuracy arbitrarily close to exact with almost-linear time, which the earlier methods the paper cites did not. - **Trust:** Formal proof listed - **Field:** Theoretical computer science (1 paper) ## The explanation Turn the word kitten into sitting. Change the k to an s. Change the e to an i. Add a g at the end. That is three edits, and no shorter route exists. The edit distance between two strings is this smallest count. Each insertion, deletion or swap of one symbol costs one. The classic method fills in a table with one cell for each pair of positions. For kitten and sitting that is 6 times 7, or 42 cells. The work grows with the product of the two lengths. Two strings of a million symbols each need about a trillion cells. Robert Wagner and Michael Fischer described this table method in 1974. Doing much better exactly looks out of reach. In 2018, Arturs Backurs and Piotr Indyk showed a link to a standard belief about hard problems. A fast exact method of a certain strong kind would break that belief. Their result says nothing against good estimates, though. So researchers turned to approximation, meaning an answer that may be off by a controlled factor. Estimates improved over two decades. In 2020, Alexandr Andoni and Negev Shekel Nosatzki reached a fixed error factor in time just above linear. Linear time means work proportional to the total length. But their factor could not be pushed close to one. In 2026, Xiao Mao and Aviad Rubinstein got within any factor 1 + ε. Here ε is a small accuracy setting, such as 0.1. Their running time was only a little below the square of the length. This paper proves that both goals can be met at once. Fix any fraction ε between 0 and 1. With probability at least 2/3, the algorithm returns a whole number between the true distance and 1 + ε times it[1]. Its expected running time is N to the power 1 + o(1), where N is the total length. That means barely more than linear: the extra factor grows slower than any fixed power of N. Equal strings always give zero[2]. Back to kitten and sitting, with ε set to 0.1. The answer must lie between 3 and 3.3. The only whole number there is 3. So a correct run gives the exact answer here. On long strings, a 10 percent error is the price for skipping most of the trillion cells. The hard part was cost, not accuracy. The method splits the first string into pieces, then pieces of pieces. It estimates how each piece lines up against stretches of the second string. Checking every possible stretch for every piece would use up the whole time budget[3]. The paper predicts where a best alignment should go from rough early estimates. That confines each piece to a narrow band of positions[4]. It then bounds how many smaller estimates are ever actually requested. The result is a statement about very long inputs. For each fixed ε, the guarantee only kicks in past some length that depends on ε. Below it, the algorithm falls back on the exact table method[5]. The paper says these thresholds are very large[6]. One condition requires the length to exceed roughly 2 raised to 2 raised to 2 to the 999th power. So this is a theorem about growth rates, not a practical tool. The paper also does not claim a good dependence on ε[7]. How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers the accuracy guarantee with probability at least 2/3 and the zero answer on equal strings. It also covers the almost-linear bound on expected work, for symbols of polynomially bounded size. A tool called Comparator matches it against a fixed reference statement. No specialists have published a review yet. **What it doesn't show.** This does not give a practical program: below enormous input lengths the method falls back on the classic quadratic table. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Major in theory if the proof holds, with a Lean check of the main theorem listed. It is an asymptotic statement with huge thresholds, it gives no practical speedup, and no specialist review is published. ## Words used - **Edit distance:** The fewest single-symbol insertions, deletions and swaps that turn one string into another. - **Approximation factor:** How far an estimate may be from the true answer, as a multiple; 1 + ε allows an ε share of error. - **Linear time:** Running time that grows in proportion to the size of the input. - **N to the 1 + o(1):** Time just above linear: the extra factor grows slower than any fixed power of N. - **Randomized algorithm:** A method that uses coin flips and must succeed only with a stated probability. - **Alignment:** A way of matching positions in one string to positions in the other. - **Comparator:** A tool that checks a Lean proof proves exactly a fixed reference statement, using only standard axioms. ## The original paper - [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf) - September 24, 2026 - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/121.md) ## Quoted lines from the paper (7) [1] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > For every fixed rational $\varepsilon$, its worst-case expected running time on strings of total length $N$ is $N^{1+o(1)}$ as $N\to\infty$ on the logarithmic-word RAM. [2] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > Equal strings return zero deterministically. [3] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > In our refinement, unrestricted recursive evaluation of child distances would consume the available time even if the resulting numerical error were small. [4] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > Requiring agreement with that prediction restricts the possible target positions at each cut to a narrow band. [5] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > Use exact dynamic programming also if $\ell<2^{1000}$ or $\ell\varepsilon<10$. [6] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > Section … gives the finite input convention and fallback rules; their thresholds are very large, so the result is an asymptotic approximation scheme. [7] From [An Almost-Linear Approximation Scheme for Edit Distance](https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf): > We do not assert polynomial dependence on $1/\varepsilon$ or a joint bound when the accuracy varies with $N$. ## Other sources - [R. A. Wagner and M. J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM 21 (1974), 168–173](https://doi.org/10.1145/321796.321811) - [A. Backurs and P. Indyk, “Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False)”, SIAM Journal on Computing 47 (2018), 1087–1097](https://doi.org/10.1137/15M1053128) - [A. Andoni and N. S. Nosatzki, “Edit Distance in Near-Linear Time: It's a Constant Factor”, FOCS (2020), 990–1001](https://doi.org/10.1109/FOCS46700.2020.00096) - [X. Mao and A. Rubinstein, “Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time”, STOC (2026), arXiv:2603.29702](https://arxiv.org/abs/2603.29702v1) - [openai/math release notes (2026): model provenance](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model” ## Related - [Polynomial-time scheduling on three identical machines](https://closedform.nishachay.tech/e/openai-math-2026-124/) - Theoretical computer science - [Exponential state costs for two-way automata](https://closedform.nishachay.tech/e/openai-math-2026-129/) - Theoretical computer science - [Subset Sum in O(2^(0.49n)) time](https://closedform.nishachay.tech/e/openai-math-2026-138/) - Theoretical computer science - [Exact derandomization of logarithmic space: L=RL=BPL](https://closedform.nishachay.tech/e/openai-math-2026-103/) - Theoretical computer science - [Deterministic polynomial factorization over prime fields](https://closedform.nishachay.tech/e/openai-math-2026-142/) - Theoretical computer science - [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results - [Open since the 1970s](https://closedform.nishachay.tech/open-since/1970s/) - Era · 63 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20121%5D%20)