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

By Jacob Steinhardt. 2017

20 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “…tradeoﬀs [DKS17c, DKK + 18], establishing connections to PAC learning [DKS17a], tolerating more noise by outputting a list of hypotheses [CSV17, MV17, DKS17b], robust estimation of discrete structures [Ste17, QV17, SCV18], and robust estimation via sum-of-squares [KS17b, HL17, KS17a].”