Planted Dense Subgraph Conjectures Are EquivalentResearch Paper
The planted clique and planted dense subgraph problems are the standard average-case hard problems behind a large family of reductions in statistics and learning theory: sparse PCA, community detection, submatrix localization, tensor PCA and robust estimation all inherit computational lower bounds from them (Brennan, Bresler, Huleihel, COLT 2018; Brennan,…