VibeMathedMath problems solved with AI
Sign in

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

Edit distance between strings of total length NN is computable in quadratic time, and Backurs and Indyk showed that a strongly subquadratic exact algorithm would refute SETH. Approximation algorithms reached polylogarithmic factors in time N1+δN^{1+\delta} (Andoni-Krauthgamer-Onak), a constant factor in subquadratic time (Chakraborty-Das-Goldenberg-Koucky-Saks), and constant factors depending on δ\delta in time N1+δN^{1+\delta} (Andoni-Nosatzki 2020). For accuracy 1+ε1+\varepsilon the best known time saved only a quasi-polynomial factor, N2/2log⁡Ω(1)NN^2/2^{\log^{\Omega(1)}N} (Mao-Rubinstein 2026). For every fixed ε>0\varepsilon>0, is there a randomized (1+ε)(1+\varepsilon)-approximation of edit distance running in time N1+o(1)N^{1+o(1)}?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Fine-grained and string algorithms
Posed by
Open question of the edit-distance approximation line (Andoni, Krauthgamer and Onak; Andoni and Nosatzki; Mao and Rubinstein); no single poser cited
Year posed
—
Years open
—
Solved
2026-09-24
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
45 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Main theorem: one randomized algorithm, uniform in a rational accuracy input ε∈(0,1)\varepsilon\in(0,1), returns for explicitly stored strings with polynomially bounded integer symbols an estimate within factor 1+ε1+\varepsilon of unit-cost edit distance with probability at least 2/3, in worst-case expected time N1+o(1)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/ε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 NN.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscripts are authored 'OpenAI' and name no human author. The single manuscript (September 24, 2026) is the whole family.

Verification

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<ε<10<\varepsilon<1, on integer lists of total length at most NN the output lies in [ed,(1+ε)ed][\mathrm{ed},(1+\varepsilon)\mathrm{ed}] with probability at least 2/3, equal strings give 0, and for symbols bounded by (N+2)C(N+2)^C the expected work is at most (N+2)1+η(N+2)^{1+\eta} for every η>0\eta>0 and large NN, 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.

Sources

Changelog1 change

Discussion