Computational Barriers in Statistical Estimation and Learning | Richard M. Karp Distinguished Lecture

It is natural to believe that an accurate model for a certain phenomenon can always be found, given enough data. How much data is "enough"? Somewhat tautologically: the data must contain enough information to identify the right model. This intuition can be made precise using statistics and information theory.

It was a recent discovery that these theories often give an overoptimistic answer. Even if the data contain enough information, no practical algorithm is known to achieve this goal. In this Richard M. Karp Distinguished Lecture, Andrea Montanari (Stanford) provides examples and surveys recent mathematical progress.