Simplicity and Complexity in Belief Propagation

Elchanan Mossel

There is a very simple algorithm for the inference of posteriors for probability Markov models on trees. Asymptotic properties of this algorithm were first studied in statistical physics and have later played a role in coding theory, in machine learning, in evolutionary inference, among many other areas. The lectures will highlight various phase transitions for this model and their connection to modern statistical inference Finally, we show that perhaps unexpectedly this "simple" algorithm requires complex computation in a number of models.