{"id":"openai-math/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent","pdf":"https://github.com/openai/math/blob/main/preprints/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026","tags":["metric-embeddings","edit-distance","combinatorics"],"score":0,"title":"Edit Distance in l1: Matching Bounds up to Constants in the Exponent","domain":"Convex and metric geometry","family":"099","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.MG","summary":"We determine the exponential scale of the least ℓ 1 distortion of unit-cost edit distance on all strings of length at most d . For every sufficiently large d , uniformly over finite alphabets of size at least two, the distortion lies between $`\\exp(c\\sqrt{\\log d\\,\\log\\log d})`$ and $`\\exp(C\\sqrt{\\log d\\,\\log\\log d})`$ for absolute constants $`c,C\\gt 0`$. The lower bound already holds on binary strings of one common length. Thus the order of logarithmic distortion is sharp up to absolute constants.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{},"formalized":false,"family_title":"The sharp exponential scale of edit-distance distortion"}