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 community detection in networks, and clustering of sparse high-dimensional data, where if our data become too sparse or too noisy it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Physics both help us to locate this phase transitions, and design optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices and spin glass theory.

Santa Fe Institute