Edit Distance in l1: Matching Bounds up to Constants in the Exponent
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent
curl -X POST /api/v1/records/openai-math/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'