{"id":"openai-math/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance","pdf":"https://github.com/openai/math/blob/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026","tags":["string-algorithms","edit-distance"],"score":0,"title":"An Almost-Linear Approximation Scheme for Edit Distance","domain":"Theoretical computer science","family":"121","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational $`\\varepsilon\\in(0,1)`$, it estimates the distance between arbitrary explicitly stored strings of total length N within a factor $`1+\\varepsilon`$ 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Almost-linear approximation of edit distance"}