Abstract:  There is a deep analogy between Bayesian inference — where we try to fit a model to data, which has a ground-truth structure partly hidden by noise — and statistical physics. Many concepts like energy landscapes, free energy, and phase transitions can be usefully carried over from physics to machine learning and computer science. At the very least, these techniques are a source of conjectures that have stimulated new work in probability, combinatorics, and theoretical computer science. At their best, they offer strong intuitions about the structure of inference problems and possible algorithms for them.

One recent success of this interface is the discovery of a phase transition in community detection in sparse graphs. Analogous transitions exist in many other inference problems, where our ability to find patterns in data jumps suddenly as a function of how noisy they are. I will discuss why and how this detectability transition occurs, review what is known rigorously, and present a number of open questions that cry out for proofs.

Bio:  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 Normale Superieure, École Polytechnique, Université Paris 7, the Niels Bohr Institute, Northeastern University, and the University of Michigan. He has published over 150 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, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.