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

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 contains enough information, no practical algorithm is known to achieve this goal. I will provide examples and survey recent mathematical progress.

If you require accommodation for communication, please contact our Access Coordinator at simonsevents [at] berkeley.edutarget="_blank" with as much advance notice as possible.