  Over-parametrization was a crucial ingredient for recent developments in
inference and machine-learning fields. However a good theory explaining this
success is still lacking. In this paper we study a very simple case of
mismatched over-parametrized algorithm applied to one of the most studied
inference problem: the planted clique problem. We analyze a Monte Carlo (MC)
algorithm in the same class of the famous Jerrum algorithm. We show how this MC
algorithm is in general suboptimal for the recovery of the planted clique. We
show however how to enhance its performances by adding a (mismatched)
parameter: the temperature; we numerically find that this over-parametrized
version of the algorithm can reach the supposed algorithmic threshold for the
planted clique problem.
