Abstract
The predominant method for computational phase transitions is to characterize the performance of restricted models of computation. For each statistical problem, researchers try to understand the performance of spectral methods, convex relaxations, message passing algorithms, low-degree polynomials, and statistical queries, among other methods. Remarkably, for many statistical problems, these methods exhibit the same computational phase transitions. Understanding why this phenomenon occurs is key to understanding the complexity of statistical problems. Can we formally prove that our leading models of computation are equivalent for a broad class of statistical problems? In this talk, I will survey some recent efforts to establish such equivalences between popular models of computation, with some focus on a recent work which establishes the equivalence of statistical query algorithms and low-degree polynomial tests for a large class of hypothesis testing problems.