Average case hardness for statistical problems

With the recent data revolution, statisticians are considering larger datasets, more sophisticated models. As a consequence, it is important to seek methods that are computationally efficient as well as statistically powerful.
We will show how hypotheses from theoretical computer science on the hardness of some problems in average case can give us a better understanding of algorithmic limitations for high-dimensional statistical problems.

We will give an overview of several results related to the planted clique problem, and study another problem involving random satisfiability formulas.