Abstract
A statistical inference problem is specified by a joint distribution $P(X,Y)$ between hidden variables $X$ and observations $Y$ on them. The computational problem of inference is to find the values of the hidden variables given a set of observations drawn from the distribution. Examples of high-dimensional inference problems include community detection in stochastic block models and planted constraint satisfaction problems.
In this series of lectures, we will explore broad classes of algorithms for statistical inference and hypothesized computational barriers for this class of inference problems. On the algorithmic front, we will see an overview of belief propagation, and the sum-of-squares semidefinite programming. On the complexity front, the lectures will cover the low-degree indistinguishability and the stable fixed point barrier, both of which lead to precise prediction of thresholds of computational intractability. Community detection in stochastic block models will be our running example through the series.