A (1+epsilon)-approximation of edit distance in almost-linear time

Main theorem: one randomized algorithm, uniform in a rational accuracy input $\varepsilon\in(0,1)$ , returns for explicitly stored strings with polynomially bounded integer symbols an estimate within factor $1+\varepsilon$ of unit-cost edit distance with probability at least 2/3, in worst-case expected time $N^{1+o(1)}$ on a logarithmic-word RAM; equal strings give 0 deterministically. The bound is pointwise in fixed $\varepsilon$ : no polynomial dependence on $1/\varepsilon$ is claimed, and exact computation is used below very large accuracy-dependent thresholds, so it is an asymptotic scheme. Not shown: an alignment or edit script, weighted costs, a deterministic algorithm, or bounds when $\varepsilon$ shrinks with $N$ .

Exact FrontierDelta

Prior state unknown→proved

Scope and record

Occurred: Sep 24, 2026

Delta type: SOURCE CLAIM

Assumptions: VibeMathed verification: lean-checked. Publication: announcement. AI contribution: ai-discovered. VibeMathed editorial classifications, scores, notes, relations, and dataset structure are CC BY 4.0. Source statements and linked content retain their own rights.

Canonical aliases: A (1+epsilon)-approximation of edit distance in almost-linear time · Near-linear (1+eps) edit distance

Confidence: Not scored

Registry verification: lean checked · announcement · candidate

Open the source record ↗

Attribution

VibeMathed
registry · event recorded by

Unreleased internal OpenAI model
model · ai model contributor · OpenAI

Evidence vector

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Named evidence

VibeMathed record: A (1+epsilon)-approximation of edit distance in almost-linear time

specialist registry · passed

No independent mathematician has checked this yet. Checked here: the abstract, introduction and main theorem were read against the question as framed. The analysis was not refereed. The challenge lean/ComparatorChallenges/EditApproximation.json (theorem OAI.EditApproximation.almostLinearEditDistanceRawBand, solution module OAI.Combinatorics.EditApproximation.Specification.RawBandMain, present at the pinned commit) is not in the formalization catalogue lean/formalization.yaml; it is found through lean/docs/121.md. Its main theorem was read here: for every binary fraction $0<\varepsilon<1$ , on integer lists of total length at most $N$ the output lies in $[\mathrm{ed},(1+\varepsilon)\mathrm{ed}]$ with probability at least 2/3, equal strings give 0, and for symbols bounded by $(N+2)^C$ the expected work is at most $(N+2)^{1+\eta}$ for every $\eta>0$ and large $N$ , with polynomial space. The algorithm and its work and space accounting are defined inside the roughly 19,000-line challenge file itself; whether that accounting matches word-RAM time was not audited here. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.