Powered by Indico
v3.2
In this talk I will focus on inference problems defined on sparse random graphs. These problems have the great advantage that can be very efficiently simulated and also solved analytically via the cavity method. For these reasons they offer a perfect playground to search for connections between phase transitions and the behavior of solving algorithms. I will present the most general scenario of phase transitions that arises from the study of the Bayesian inference problems. Then I will discuss the behavior of two different classes of solving algorithms: message passing algorithms (Belief Propagation) and Monte Carlo based algorithms. For the latter class, which is much more robust than the former, we have recently presented a theory, that I will illustrate, explaining the performances and predicting the algorithmic thresholds.