  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=\Theta(n^{\alpha}), \alpha \in
(0,1/2)$, which is planted in the Erd\H{o}s-R\'{e}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+\epsilon) \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 =
\Omega(\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=\Theta(n^{\alpha})$ for any constant $0
\leq \alpha < 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).
