迹重构的定量下界
Quantitative lower bounds for trace reconstruction
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究二元字从独立删除迹中的最坏情况精确重构。作者声称对每个固定删除概率q∈(0,1)，即使计算不受限且成功概率为任意固定正数，也需n^{Ω(log log n)}个样本；这否定二元迹重构的多项式样本问题。更一般地，当q^3 log n趋于无穷时，证明对每个固定0<c<1/(4 log 2)需n^{c log(q^3 log n)}个样本。若成立，将给出迹重构样本复杂度的强下界。
- 二元迹重构最坏情况需n^{Ω(log log n)}样本，否定多项式样本可能。
- 下界对任意固定删除概率与任意固定正成功概率成立。
- 更一般地给出n^{c log(q^3 log n)}形式的样本下界。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
Exact worst-case reconstruction of a binary word from independent deletion traces requires $`n^{\Omega(\log\log n)}`$ samples for every fixed deletion probability $`q\in(0,1)`$, even with unrestricted computation and any fixed positive success probability. This gives a negative answer to the polynomial-sample question for binary trace reconstruction. More generally, when $`q^3\log n\to\infty`$, we prove a lower bound of $`n^{c\log(q^3\log n)}`$ samples for every fixed $`0\lt c\lt 1/(4\log2)`$. Here q is the known deletion probability, and all logarithms are natural.
用户标记：未标记
固定编号：a6b826743e07e4fa
原文来源