Does robustness imply tractability? A lower bound for planted clique in the semi-random model

We consider a robust analog of the planted clique problem. In this analog, a set S of vertices is chosen and all edges in S are included; then, edges between S and the rest of the graph are included with probability frac12, while edges not touching S are allowed to vary arbitrarily. For this semi-random model, we show that the information-theoretic threshold for recovery is tildeTheta(√n), in sharp contrast to the classical information-theoretic threshold of Theta(log(n)). This matches the conjectured computational threshold for the classical planted clique problem, and thus raises the intriguing possibility that, once we require robustness, there is no computational-statistical gap for planted clique. Our lower bound involves establishing a result regarding the KL divergence of a family of perturbed Bernoulli distributions, which may be of independent interest.