We introduce a framework for proving lower bounds on computational problems over
distributions, based on defining a restricted class of algorithms called 
statistical algorithms. 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. Our definition captures most natural algorithms of interest
in theory and in practice, e.g., moments-based methods, local search and
standard iterative methods for convex optimization.
 For several well-known problems over distributions, we give lower bounds on
the complexity of any statistical algorithm. These include a nearly optimal
lower bound for detecting planted bipartite clique.