论文标题
从痕迹的底带密度估计
Substring Density Estimation from Traces
论文作者
论文摘要
在跟踪重建问题中，人们试图从一系列痕迹中重建二进制字符串$ s $，每种痕迹都是通过通过删除频道传递$ s $获得的。众所周知，$ \ exp（\ tilde o（n^{1/5}））$ tracs足以重建具有高概率的任何长度 - $ n $ string。我们考虑了痕量重建问题的变体，其中的目标是恢复“密度图”，该“密度图”表明每个长度 - $ k $ substring in $ s $。我们表明，$ε^{ - 2} \ cdot \ text {poly}（n）$ tracs tracs足以在最多$ε$中恢复密度映射。结果，当仅限于一组源字符串，其最小“密度映射距离”至少为$ 1/\ text {poly}（n）$时，可以用多个多个轨迹来解决痕量重建问题。
In the trace reconstruction problem, one seeks to reconstruct a binary string $s$ from a collection of traces, each of which is obtained by passing $s$ through a deletion channel. It is known that $\exp(\tilde O(n^{1/5}))$ traces suffice to reconstruct any length-$n$ string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a "density map" that indicates the locations of each length-$k$ substring throughout $s$. We show that $ε^{-2}\cdot \text{poly}(n)$ traces suffice to recover the density map with error at most $ε$. As a result, when restricted to a set of source strings whose minimum "density map distance" is at least $1/\text{poly}(n)$, the trace reconstruction problem can be solved with polynomially many traces.
