Complexity, Phase Transitions, and Inference by Cristopher Moore (Part 3)

There is a deep analogy between statistical inference and statistical physics. I will give a friendly introduction to both of these fields. I will then discuss phase transitions in problems like community detection in networks, and clustering of sparse high-dimensional data, where if our data becomes too sparse or too noisy it becomes impossible to find the underlying pattern; moreover, I will discuss optimal algorithms that succeed as well as possible up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory. This lecture is part of Games, Epidemics and Behavior Table of Contents (powered by https://videoken.com) 0:00:00 SCIENCES 0:00:04 imed at specialists.