Almost-linear approximation of edit distance

1 · The essentials

Edit distance measures how many single-symbol insertions, deletions, or replacements are needed to turn one string into another. The manuscript describes a randomized method for estimating this number rather than calculating it exactly. For any fixed rational accuracy setting $ε$ between zero and one, its estimate is within a factor of $1 + ε$ of the true distance with probability at least two-thirds. Its expected running time grows almost linearly with the combined length of the strings, in an asymptotic sense. This guarantee applies to explicitly stored strings whose symbols are integers with polynomially bounded values. If the two strings are equal, the method always returns zero. The main result has a Lean formalization, although the supplied material does not specify its detailed coverage.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine comparing two typed shopping lists by counting the fewest character insertions, deletions, and replacements needed to make them match. The method resembles a randomized estimator of that count, with a chosen relative accuracy rather than a promise of the exact answer. The image does not explain how the estimator achieves its running time.

Why it matters

The result combines a relative approximation guarantee with almost-linear expected running time for arbitrary strings satisfying the stated input conditions. Accuracy can be chosen arbitrarily close to exactness by fixing a sufficiently small positive rational $ε$ . However, this is a large-input guarantee at fixed accuracy, not a stated bound on practical performance.

2 · Going further

The problem is to estimate unit-cost edit distance between two explicitly stored strings of total length $N$ . Each insertion, deletion, or substitution has cost one. For every fixed rational $ε \in (0, 1)$ , the manuscript states a uniform randomized scheme that estimates this distance within a multiplicative factor $1 + ε$ , with success probability at least $2/3$ . Equal strings receive the answer zero deterministically.

The stated computational model is a logarithmic-word RAM, and symbols are integers from a polynomially bounded alphabet. The running-time guarantee is worst-case expected time $N^{1 + o (1)}$ : the exponent approaches one as $N$ grows, with $ε$ held fixed. The expectation concerns the algorithm's random choices; it is not an average over a distribution of inputs.

The supplied abstract states the algorithmic guarantee but does not describe the construction or the main idea of its argument. It also provides no comparison with earlier bounds or historical context. Only the main manuscript is supplied, so no relationship to companion manuscripts can be established from this material. The main result has a Lean formalization, but the supplied text does not identify which implementation details or subsidiary claims it covers.

Useful notions

Strings and symbol operations
Multiplicative approximation
Randomized algorithms and success probability
Expected running time
Asymptotic growth and little-o notation

What was known before / what is new

Before

The source frames the task as approximating unit-cost edit distance between explicitly stored strings. It does not state earlier algorithms, previous running-time bounds, or a historical open problem, so no specific prior baseline can be given.

New

The manuscript presents a uniform randomized approximation scheme with factor $1 + ε$ and worst-case expected time $N^{1 + o (1)}$ for each fixed rational $ε \in (0, 1)$ . Its stated guarantees include success probability at least $2/3$ , support for polynomially bounded integer alphabets, and deterministic zero output on equal strings. The main result has a Lean formalization.

Limits and assumptions

The guarantee concerns unit-cost edit distance, explicitly stored inputs of total length $N$ , polynomially bounded integer symbols, and a logarithmic-word RAM. The accuracy parameter must be a fixed rational number in $(0, 1)$ ; the source does not give a running-time dependence on that parameter or a guarantee when it varies with input length. Running time is bounded in expectation, and the general approximation guarantee has success probability at least $2/3$ , not certainty. The main result has a Lean formalization, but its detailed scope is not supplied, so coverage of every claim cannot be asserted. The supplied material identifies no remaining open problems and provides no algorithmic proof details.

Mini glossary

Unit-cost edit distance: The smallest number of single-symbol insertions, deletions, and substitutions needed to transform one string into another, counting each operation as one.
Multiplicative approximation: An estimate whose accuracy is expressed by a factor relative to the true value, here $1 + ε$ .
Worst-case expected time: A running-time bound that holds for every allowed input after averaging over the algorithm's random choices.
Almost-linear time: Here, the asymptotic bound $N^{1 + o (1)}$ , whose exponent approaches one as input length grows at fixed accuracy.
Logarithmic-word RAM: The stated computation model, using random-access memory with words whose length grows logarithmically with input size.

Keywords : Edit distance · Randomized approximation · Almost-linear time

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

For every fixed rational $ε \in (0, 1)$ , gives a randomized $(1 + ε)$ approximation to unit-cost edit distance in worst-case expected time $N^{1 + o (1)}$ , with success probability at least 2/3. The strings have total length N and polynomially bounded integer symbols. This is an asymptotic guarantee at fixed accuracy.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/121.md

Manuscripts in this family

★

An Almost-Linear Approximation Scheme for Edit Distance

24/09/2026

To be verified

We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational $ε \in (0, 1)$ , it estimates the distance between arbitrary explicitly stored strings of total length N within a factor $1 + ε$ with probability at least 2/3, in worst-case expected time $N^{1 + o (1)}$ on a logarithmic-word RAM. The algorithm supports polynomially bounded integer alphabets and returns zero deterministically on equal strings.

PDF GitHub folder