Parallel tempering for the planted clique problem
The theoretical information threshold for the planted clique problem is 2 log(2) (N), but no polynomial algorithm is known to recover a planted clique of size O(N1/ 2-epsilon), epsilon > 0. In this paper we will apply a standard method for the analysis of disordered models, the parallel tempering (PT) algorithm, to the clique problem, showing numerically that its time-scaling in the hard region is indeed polynomial for the analyzed sizes. We also apply PT to a different but connected model, the sparse planted independent set problem.