daff682411a64632e083b9d6665b1d30-Supplemental-Conference.pdf

Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physics that are based on free energy landscapes. This paper aims to make a rigorousconnectionbetween the seeminglydifferent low-degreeand free-energybased approaches. We define a free-energybasedcriterionfor hardnessand formallyconnectit to the well-establishednotionof low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal.