Almost-Linear Planted Cliques Elude the Metropolis Process

Understand

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})$.