Belief-propagation, evolutionary inference, phase transitions, and complexity
There is a very simple algorithm for the inference on trees. This algorithm, known as Belief Propagation" is widely used in coding theory, machine learning, and evolutionary inference, among many other areas. The talk will be devoted to deep connections between different aspects of this algorithm and its applications in different areas.
We will highlight the interplay between Belief Propagation, linear estimators (statistics), the Kesten-Stigum bound (probability), and Replica Symmetry Breaking (statistical physics). We will discuss the role of Belief Propagation in proving phase transitions for phylogenetic reconstruction in evolutionary biology and in optimal algorithms for inference of block models in statistics and machine learning. Finally, we will discuss the computational complexity of this simple" algorithm.