  The prototypical high-dimensional statistics problem entails finding a
structured signal in noise. Many of these problems exhibit an intriguing
phenomenon: the amount of data needed by all known computationally efficient
algorithms far exceeds what is needed for inefficient algorithms that search
over all possible structures. A line of work initiated by Berthet and Rigollet
in 2013 has aimed to explain these statistical-computational gaps by reducing
from conjecturally hard average-case problems in computer science. However, the
delicate nature of average-case reductions has limited the applicability of
this approach. In this work we introduce several new techniques to give a web
of average-case reductions showing strong computational lower bounds based on
the planted clique conjecture using natural problems as intermediates. These
include tight lower bounds for Planted Independent Set, Planted Dense Subgraph,
Sparse Spiked Wigner, Sparse PCA, a subgraph variant of the Stochastic Block
Model and a biased variant of Sparse PCA. We also give algorithms matching our
lower bounds and identify the information-theoretic limits of the models we
consider.
