SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Average case hardness for statistical problems

Quentin Berthet,

Date and Time: Nov 12, 2014 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

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.