14. Dec 2020
Belief-propagation, evolutionary inference, phase transitions, and complexity
Datum: 14. December 2020 |
16:00 –
17:00
Sprecher:
Elchanan Mossel, Massachusetts Institute of Technology
Veranstaltungsort: Online on Zoom
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.