Browse › Convex and metric geometry › 099 The sharp exponential scale of edit-distance distortion
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give two finite-circle constructions of binary strings whose least ℓ1 distortion is $\exp(\Omega(\sqrt{\log d\,\log\log d}))$, where d bounds their length. Both constructions supply words of one common length for every sufficiently large cap. Two direct binary coding arguments transfer the constructions with absolute distortion and logarithmic block width. We also develop the overlapping-substring method of Ostrovsky and Rabani into a complete finite histogram embedding at the same exponential scale, uniformly over all finite alphabets and all words of length at most d, including the empty word.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, The sharp exponential scale of edit-distance distortion: Lean scope note (OpenAI Math release, lean/docs/099.md, 2026). The release's scope note lists a comparator statement (FiniteCircle.lean) covering both finite-circle lower constructions, their binary coding transfers, and the finite histogram upper embedding, uniformly over finite alphabets and including the empty word. [family-level]
Possibly relevant literature (found by the agent, not checked)
- G. Cormode and S. Muthukrishnan, The string edit distance matching problem with moves (ACM Transactions on Algorithms 3(1), 2007). Embeds edit distance with substring moves into L1 with O(log n log* n) distortion; related to the moves-based expansion estimate in the paper's histogram upper construction (Section 8).
- M. Charikar and R. Krauthgamer, Embedding the Ulam metric into ℓ1 (Theory of Computing 2, Article 11, 2006). Proves O(log n) ℓ1 distortion for edit distance on permutations, a comparison point for the alphabet-uniform constants in Theorem 1.1 and for the role of repeated symbols in the lower constructions.
- A. Andoni and K. Onak, Approximating Edit Distance in Near-Linear Time (arXiv:1109.5635, 2011). Gives a near-linear-time 2^{Õ(√log n)} approximation for edit distance, an algorithmic counterpart to the overlapping-substring recursion of Ostrovsky and Rabani that the paper's histogram embedding develops.
Digests and expositions
- Latent Seminar, Edit distance in L1: alignment obstructions and matching exponential scales (6 October 2026). This exposition compares the three manuscripts' alignment obstructions, Fourier arguments, binary transfers, and upper embeddings, explicitly stating that it does not independently verify the complete proofs. [family-level]
Elsewhere
- Emergent Mind: family 099
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Finite-Circle-Obstructions-Binary-Codes-and-Histogram-Embeddings-for-Edit-Distance-September-27-2026,
author = {{OpenAI}},
title = {{Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Finite-Circle-Obstructions-Binary-Codes-and-Histogram-Embeddings-for-Edit-Distance-September-27-2026/paper.pdf}{OAI:Finite-Circle-Obstructions-Binary-Codes-and-Histogram-Embeddings-for-Edit-Distance-September-27-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/099.md. The Lean statements have not been checked by people against the paper's claims.
Family 099: The sharp exponential scale of edit-distance distortion
Determines the least distortion of embedding edit distance on words of length at most d into real ℓ1: it is $\exp(\Theta(\sqrt{\log d\,\log\log d}))$. Insertions, deletions and substitutions have unit cost. The constants are uniform over all finite alphabets with at least two symbols, even when the alphabet grows with d; binary words already force the lower bound.
Other papers in this family:
- Edit Distance in l1: Matching Bounds up to Constants in the Exponent · September 27, 2026
- Tree Constructions for the l1 Distortion of Binary Edit Distance · September 27, 2026