Does robustness imply tractability? A lower bound for planted clique in the semi-random model
This addresses the fundamental question of whether robustness implies tractability in computational complexity, with implications for understanding gaps in statistical and computational limits, though it is incremental as it builds on existing planted clique research.
The paper tackles the problem of robust recovery in a semi-random planted clique model, showing that the information-theoretic threshold is φ(√n), contrasting with the classical Θ(log n) threshold and aligning with the conjectured computational threshold, suggesting no computational-statistical gap under robustness.
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Θ(\sqrt{n})$, in sharp contrast to the classical information-theoretic threshold of $Θ(\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.