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. The talk is based on joint work with Matthew Brennan (https://arxiv.org/abs/2005.08099).