Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices

We consider two closely related problems: planted clustering and submatrix localization. In the planted clustering problem, a random graph is generated based on an underlying cluster structure of t...