Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPUTATIONAL-STATISTICAL GAP:
Reports tagged with computational-statistical gap:
TR17-069 | 17th April 2017
Jacob Steinhardt

#### 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 ... more >>>

ISSN 1433-8092 | Imprint