ISL Colloquium
The ISL Colloquium convenes in person again (on Thursdays at 4pm PT in Packard 101) as of Fall 2021. For those unable to attend, talks are also streamed via Zoom. To avoid "Zoom-bombing", we ask attendees to input their email address here to receive the Zoom meeting details via email.

← List all talks ...

Connecting Statistical Problems with Different Structures

Guy Bresler – Professor, MIT

Thu, 2-Dec-2021 / 4:00pm / Packard 101


In this talk I will describe some simple average-case reduction techniques and use these techniques to connect several statistical problems with widely varying structures. These reduction techniques transform the probability distribution defining a problem in an algorithmically efficient way while preserving the strength of the underlying signal, thereby transferring the computational phase transitions from one problem to another. We’ll focus especially on the mixtures of linear regressions problem, and show how this supervised learning problem over continuous variables can be precisely related to the planted clique problem, a combinatorial unsupervised learning problem. Along the way we’ll see a method for turning positive correlations into negative correlations amongst a subset of variables without knowing which subset is the correlated one, as well as a clean but non-obvious way to turn a supervised learning problem into an unsupervised one. The talk is based on joint work with Matthew Brennan (


Guy Bresler is an associate professor in the Department of Electrical Engineering and Computer Science at MIT, and a member of LIDS and IDSS. Previously, he was a postdoc at MIT and before that completed his PhD in the Department of EECS at UC Berkeley. His undergraduate degree is from the University of Illinois at Urbana-Champaign. A major focus of his research is on the computational complexity of statistical inference, a direction that combines his interests in information theory, probability, and computation.