  The planted clique problem is a paradigmatic model of
statistical-to-computational gaps: the planted clique is
information-theoretically detectable if its size $k\ge 2\log_2 n$ but
polynomial-time algorithms only exist for the recovery task when $k=
\Omega(\sqrt{n})$. By now, there are many simple and fast algorithms that
succeed as soon as $k = \Omega(\sqrt{n})$. Glaringly, however, no MCMC approach
to the problem had been shown to work, including the Metropolis process on
cliques studied by Jerrum since 1992. In fact, Chen, Mossel, and Zadik recently
showed that any Metropolis process whose state space is the set of cliques
fails to find any sub-linear sized planted clique in polynomial time if
initialized naturally from the empty set. Here, we redeem MCMC performance for
the planted clique problem by relaxing the state space to all vertex subsets
and adding a corresponding energy penalty for missing edges. With that, we
prove that energy-minimizing Markov chains (gradient descent and a
low-temperature relaxation of it) succeed at recovering planted cliques of size
$k = \Omega(\sqrt{n})$ if initialized from the full graph. Importantly,
initialized from the empty set, the relaxation still does not help the gradient
descent find sub-linear planted cliques. We also demonstrate robustness of
these Markov chain approaches under a natural contamination model.
