编辑距离的有限圆障碍、二进制码与直方图嵌入
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件给出两种有限圆构造的二进制串，其最小ℓ1失真为exp(Ω(√(log d log log d)))，其中d限制串长。两种构造对每个足够大的容量提供同一公共长度的词。两个直接二进制编码论证以绝对失真和对数块宽转移构造。作者还将Ostrovsky–Rabani的重叠子串方法发展为完整的有限直方图嵌入，在同一指数尺度上对所有有限字母表和长度至多d的词（包括空词）一致成立。
- 构造二进制串使编辑距离到ℓ1的最小失真达exp(Ω(√(log d log log d)))。
- 两种构造对足够大容量提供公共长度的词。
- 发展有限直方图嵌入，统一覆盖所有有限字母表和短词。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
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.
用户标记：未标记
固定编号：36f53a8edbd0023d
原文来源