OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
For every fixed rational ε∈(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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
An Almost-Linear Approximation Scheme for Edit Distance
We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational ε∈(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…
Full source abstract
We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational ε∈(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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.