二进制编辑距离ℓ1扭曲的树构造
Tree Constructions for the l1 Distortion of Binary Edit Distance
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件给出两种独立构造，对每个充分大的d，产生长度至多d的等长二进制词，其普通编辑距离度量需要ℓ1扭曲exp(Ω(√(log d log log d)))。作者还证明了一个针对指定输入长度的常数扭曲二进制转换。结合伴随的上嵌入定理，这些下界在至少两个符号的有限字母表上一致确定了对数扭曲的阶。
- 两种独立构造给出二进制词编辑距离的ℓ1扭曲下界。
- 下界为exp(Ω(√(log d log log d)))，对充分大d成立。
- 结合上嵌入定理，确定有限字母表上对数扭曲的阶。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
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.
用户标记：未标记
固定编号：784e0d2f1d62dbdd
原文来源