In recent years, the field of high-dimensional statistics has increasingly confronted a fundamental question: when are the signals we aim to recover not only statistically identifiable but also within reach of efficient algorithms? This question is not only relevant from a theoretical point of view, but has also practical implications across various fields, from machine learning and cryptography to communication networks and finance. Relying on methods from statistical physics of spin glasses, this thesis describes a coherent perspective in which message passing techniques, free energy principles, and phase transitions give a very effective way to study computational hardness in many interesting settings. The fundamental fact we employ is that many problems in statistical inference can be recast as the study of disordered systems at thermal equilibrium, for which we have decades of work to rely on.
We start by making this connection explicit in the introduction, where we outline the key concepts and tools from statistical physics that will be employed throughout the thesis.
Part~I then focuses on the problem of Bayesian inference for spreading processes on graphs. We first study the phase diagram of the case in which partial observations are available for classical epidemic models, like the SI and SIR models.
We then analyse the impact of incorporating structured priors, through the lens of Generalised Linear Models (GLMs), on the inference process. We show how adding these ``contextual'' information can both enhance recovery and, in some settings, trigger sharp transitions in the inference, that define computationally hard phases.
The ``Intermezzo'' chapter is meant as a bridge between the study of inference problems of PartI and the analysis of sampling algorithms presented in PartII@. It first reviews different methods that were used in the statistical physics literature to characterize metastability in disordered systems as spin glasses, establishing some connections between them. It then shows how to use these tools to derive a mathematically rigorous statement about how the existence of these metastable states at high temperatures imply lower bounds on the mixing time of Langevin dynamics when initialised near these states.
Part~II evaluates flow-based, diffusion-based, and autoregressive generative models as samplers for known probabilistic measures. By formulating these methods as sequences of Bayes-optimal denoising steps, it establishes performance limits and advantages relative to Langevin/MCMC@. Two broad conclusions emerge. In systems with a Random First Order Theory (RFOT) phase transition, generative samplers encounter intrinsic denoising barriers in regions where classical dynamics still equilibrate, highlighting limitations of these modern techniques. In contrast, for inference problems with statistical-to-computational gaps, transport-based approaches can access regimes that are out of reach for naive MCMC methods, indic
