Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

Guy Bresler, Tianze Jiang

Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as…