MIT-Harvard CINCS (Communications Information Networks Circuits and Signals) / Hamilton Institute Seminar
Speaker: Professor Cristopher Moore, Santa Fe Institute
Title: "Complexity, Phase Transitions, and Inference"
Abstract: There is a deep analogy between Bayesian inference and statistical physics. Whenever we try to fit a
model to noisy data, we can think about the “energy landscape" of possible models, and look for phase transitions
where the ground truth suddenly gets lost in this landscape. I’ll use this framework to describe a phase transition in
community detection in networks, where communities suddenly become hard or impossible to find. I will discuss
why and how this detectability transition occurs, look at related spectral algorithms, and give a hint of similar phase
transitions in other inference problems.
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, the University of Michigan, and Microsoft Research. 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.