**Title:** Reducibility Amongst Statistical Problems

**Speaker: **Guy Bresler**Date and Time: **04/21/2022 4:10PM ET**Location:** Phillips 233 and Zoom

**Abstract**: In this talk I will describe a few simple average-case reduction techniques and use these techniques to show how the computational phase transitions in a variety of statistical problems with widely varying structures all follow from a slight generalization of the planted clique conjecture. Some of these problems are robust sparse linear regression, tensor PCA, and certain dense stochastic block models. Average-case reductions transform one distribution to another, while approximately preserving the information content of the problems, and to reason about them requires a combination of ideas from complexity theory, information theory, and high-dimensional probability. The talk is based on joint work with Matthew Brennan (https://arxiv.org/abs/2005.08099).

**Bio**: Guy Bresler is an associate professor in the Department of Electrical Engineering and Computer Science at MIT, and a member of LIDS and IDSS. A major focus of his research is on trying to understand the various problem features that together dictate the computational complexity of statistical inference, a direction that combines his interests in information theory, probability, and computation.