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 becomes too sparse or too noisy it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.
Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. Since 2012, Moore has been a resident professor at the Santa Fe Institute; he has also held visiting positions at …cole Polytechnique, …cole Normale Superieure, the University of Michigan, and Northeastern University. He has published over 130 papers at the boundary between physics and computer science, ranging from quantum computing, to phase transitions in NP-complete problems, to the theory of social networks and efficient algorithms for analyzing their structure. He is an elected Fellow of the American Physical Society and the American Mathematical Society. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.