论文标题
蜘蛛图的痕量重建问题
The trace reconstruction problem for spider graphs
论文作者
论文摘要
我们研究蜘蛛图的痕量重建问题。令$ n $为蜘蛛的节点数量，而$ d $是每条腿的长度，并假设我们从删除通道中为蜘蛛的独立痕迹提供了蜘蛛的独立痕迹，在该通道中，每个非根节点均以概率$ q $删除。这是在理论计算机科学中对字符串跟踪重建问题的自然概括，这与蜘蛛具有一条腿的特殊情况相对应。在$ d \ ge \ log_ {1/q}（n）$的制度中，可以将问题简化为Vanilla字符串跟踪重建问题。因此，我们研究了更有趣的制度$ d \ le \ log_ {1/q}（n）$，其中蜘蛛的整腿都被删除了不可忽略的概率。我们描述了一种算法，该算法使用$ \ exp \ left（\ Mathcal {o} \ left（\ frac {（nq^d）^{1/3}} {d^{1/3}}（1/3}}}（\ log n）（\ log n）^{2/3} {2/3} \ right）\ right）我们的算法适用于所有删除概率$ q \ in（0,1）$。
We study the trace reconstruction problem for spider graphs. Let $n$ be the number of nodes of a spider and $d$ be the length of each leg, and suppose that we are given independent traces of the spider from a deletion channel in which each non-root node is deleted with probability $q$. This is a natural generalization of the string trace reconstruction problem in theoretical computer science, which corresponds to the special case where the spider has one leg. In the regime where $d\ge \log_{1/q}(n)$, the problem can be reduced to the vanilla string trace reconstruction problem. We thus study the more interesting regime $d\le \log_{1/q}(n)$, in which entire legs of the spider are deleted with non-negligible probability. We describe an algorithm that reconstructs spiders with high probability using $\exp\left(\mathcal{O}\left(\frac{(nq^d)^{1/3}}{d^{1/3}}(\log n)^{2/3}\right)\right)$ traces. Our algorithm works for all deletion probabilities $q\in(0,1)$.
