Almost-Linear Planted Cliques Elude the Metropolis Process

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 α ), α ∈ (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 ≥ (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 = Ω( √ n), while no polynomial-time algorithm is known to work when k = o( √ n). The computational problem of finding a planted clique of k = o( √ n) is now widely considered as a foundational problem in the study of computational-statistical gaps. 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 ≤ α < 1, unlike many other efficient algorithms that succeed when α > 1/2. Moreover, we strengthen Jerrum's results in a number of other ways including: