论文标题
shot弹枪装配阈值的晶格标签模型
Shotgun assembly threshold for lattice labeling model
论文作者
论文摘要
我们研究了晶格标签模型的shot弹枪装配问题，其中I.I.D.统一标签被分配给每个顶点的$ d $尺寸盒子长度$ n $。我们希望在整个盒子上恢复标签配置，并给定标签配置的经验概况，这些侧面长度$ r $。我们确定从不可能恢复的概率趋于趋势到1的阈值，以有效的算法恢复，概率趋于1。我们的结果在Mossel and Ross（2019）的先前工作中持续不断地提高了一个问题，从而解决了其中的问题。
We study the shotgun assembly problem for the lattice labeling model, where i.i.d. uniform labels are assigned to each vertex in a $d$-dimensional box of side length $n$. We wish to recover the labeling configuration on the whole box given empirical profile of labeling configurations on all boxes of side length $r$. We determine the threshold around which there is a sharp transition from impossible to recover with probability tending to 1, to possible to recover with an efficient algorithm with probability tending to 1. Our result sharpens a constant factor in a previous work of Mossel and Ross (2019) and thus solves a question therein.
