论文标题
种植的$ k $因素问题
The planted $k$-factor problem
论文作者
论文摘要
我们考虑恢复未知$ K $因素的问题，该问题隐藏在加权随机图中。对于$ k = 1 $，这是种植的匹配问题，而$ k = 2 $ case与种植的旅行推销员问题密切相关。通过利用通过使用两个不同的分布来对种植的子图的边缘上和外部的权重来解决的信息来解决推断问题。我们认为，在较大的尺寸限制中，可以作为信噪比的函数在完整恢复阶段和部分恢复阶段之间出现相变。我们为过渡的位置提供标准。
We consider the problem of recovering an unknown $k$-factor, hidden in a weighted random graph. For $k=1$ this is the planted matching problem, while the $k=2$ case is closely related to the planted travelling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition.
