Talk Information 04/21/2022

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.