ECCC-Report TR17-069https://eccc.weizmann.ac.il/report/2017/069Comments and Revisions published for TR17-069en-usSun, 23 Apr 2017 09:56:01 +0300
Paper TR17-069
| Does robustness imply tractability? A lower bound for planted clique in the semi-random model |
Jacob Steinhardt
https://eccc.weizmann.ac.il/report/2017/069We 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.Sun, 23 Apr 2017 09:56:01 +0300https://eccc.weizmann.ac.il/report/2017/069