Family 099Convex and metric geometryNo LeanNot yet digested

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.

Manuscripts in this family · 3

Edit Distance in l1: Matching Bounds up to Constants in the Exponent

Sep 27, 2026·paper.pdf

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.

Full abstract

PDF on GitHub LaTeX source

Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance

Sep 27, 2026·paper.pdf

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.

Full abstract

PDF on GitHub LaTeX source

Tree Constructions for the l1 Distortion of Binary Edit Distance

Sep 27, 2026·paper.pdf

We give two independent constructions of binary words of one length at most d whose ordinary edit-distance metrics require ℓ

_{1}

distortion

\exp(\Omega(\sqrt{\log d\,\log\log d}))

for every sufficiently large d. We also prove a constant-distortion binary conversion for one prescribed input length. Together with the companion upper embedding theorem, these lower bounds determine the order of logarithmic distortion uniformly over finite alphabets with at least two symbols.

Full abstract

PDF on GitHub LaTeX source