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
$\frac{1}{2}$, 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 $\tilde{\Theta}(\sqrt{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.
