论文标题
几乎是线性种植的集团躲避了大都市的过程
Almost-Linear Planted Cliques Elude the Metropolis Process
论文作者
论文摘要
Jerrum（1992）的开创性作品表明，大集团躲避了大都市的过程。更具体地说，Jerrum表明，Metropolis算法找不到大小$ k =θ（n^α），α\ in（0,1/2）$的集团，该算法在erdős-rényi随机图$ g（n，1/2）$中种植在（0,1/2）$中。从理论上讲，可以在$ k \ ge（2+ε）\ log n $的情况下找到此类种植的集团。 Since the work of Jerrum, the computational problem of finding a planted clique in $G(n,1/2)$ was studied extensively and many polynomial time algorithms were shown to find the planted clique if it is of size $k = Ω(\sqrt{n})$, while no polynomial-time algorithm is known to work when $k=o(\sqrt{n})$.值得注意的是，该问题算法硬度的第一个证据通常归因于1992年的Jerrum的结果。 在本文中，我们重新审视了Jerrum建议的原始大都市算法。有趣的是，我们发现，对于任何常数$ 0 \ leqα<1 $，大都市算法实际上未能恢复一个大小$ k =θ（n^α）$的种植集团。 此外，我们以其他多种方式加强了Jerrum的结果，包括：像MCMC文献中的许多结果一样，Jerrum的结果表明，Metropolis算法失败的起始状态（可能取决于实例）。对于各种温度，我们表明算法以最自然的初始状态（即空的集团）启动时失败。这回答了Jerrum（1992）中指出的一个空旷的问题。我们还表明，Metropolis算法的模拟回火版本（它的更复杂的温度交换变体）也在相同的参数方面失败。 最后，我们的结果证实了Gamarnik和Zadik（2019）以及Fachin，de Feo（2021）的最新预测。
A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size $k=Θ(n^α), α\in (0,1/2)$, which is planted in the Erdős-Rényi random graph $G(n,1/2)$, in polynomial time. Information theoretically it is possible to find such planted cliques as soon as $k \ge (2+ε) \log n$. Since the work of Jerrum, the computational problem of finding a planted clique in $G(n,1/2)$ was studied extensively and many polynomial time algorithms were shown to find the planted clique if it is of size $k = Ω(\sqrt{n})$, while no polynomial-time algorithm is known to work when $k=o(\sqrt{n})$. Notably, the first evidence of the problem's algorithmic hardness is commonly attributed to the result of Jerrum from 1992. In this paper we revisit the original Metropolis algorithm suggested by Jerrum. Interestingly, we find that the Metropolis algorithm actually fails to recover a planted clique of size $k=Θ(n^α)$ for any constant $0 \leq α< 1$. Moreover, we strengthen Jerrum's results in a number of other ways including: Like many results in the MCMC literature, the result of Jerrum shows that there exists a starting state (which may depend on the instance) for which the Metropolis algorithm fails. For a wide range of temperatures, we show that the algorithm fails when started at the most natural initial state, which is the empty clique. This answers an open problem stated in Jerrum (1992). We also show that the simulated tempering version of the Metropolis algorithm, a more sophisticated temperature-exchange variant of it, also fails at the same regime of parameters. Finally, our results confirm recent predictions by Gamarnik and Zadik (2019) and Angelini, Fachin, de Feo (2021).
