Overview of message passing algorithms and their use in statistical physics

Message-passing algorithms such as belief propagation or approximate message passing provide asymptotically exact solutions to a class of disordered statistical physics models. Developed in the fields of spin glasses, they can be used way more broadly as both algorithmic tools to obtain thermodynamic averages on a given instance of the problem or as analysis tools leading to results equivalent to those that can be obtained via the replica or the cavity method. In this talk, we will review the usage of these algorithms in statistical physics but also in computational problems such as community detection, compressed sensing or training of simple neural networks. We will also compare to the more commonly used methods based on Monte Carlo Markov Chains or the Langevin dynamics.