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 …