  We introduce a framework for proving lower bounds on computational problems
over distributions against algorithms that can be implemented using access to a
statistical query oracle. For such algorithms, access to the input distribution
is limited to obtaining an estimate of the expectation of any given function on
a sample drawn randomly from the input distribution, rather than directly
accessing samples. Most natural algorithms of interest in theory and in
practice, e.g., moments-based methods, local search, standard iterative methods
for convex optimization, MCMC and simulated annealing can be implemented in
this framework. Our framework is based on, and generalizes, the statistical
query model in learning theory (Kearns, 1998).
  Our main application is a nearly optimal lower bound on the complexity of any
statistical query algorithm for detecting planted bipartite clique
distributions (or planted dense subgraph distributions) when the planted clique
has size $O(n^{1/2-\delta})$ for any constant $\delta > 0$. The assumed
hardness of variants of these problems has been used to prove hardness of
several other problems and as a guarantee for security in cryptographic
applications. Our lower bounds provide concrete evidence of hardness, thus
supporting these assumptions.
