University of Iowa "Ida Cordelia Beam Distinguished Visiting Professor" 2026-27
Cristopher Moore, Ph.D., Resident Professor, Santa Fe Institute

Abstract
Many NP-complete problems undergo physics-like phase transitions. Problems like Boolean satisfiability or graph coloring suddenly become unsatisfiable when the number of constraints or edges passes a critical threshold. This also happens in problems in statistical inference and data science, like finding communities in networks or approximate factorizations of matrices or tensors of noisy data. An emerging picture suggests that these problems often have three regimes: an “easy” range where simple algorithms work, an “impossible” regime where no amount of computation can succeed, and a “hard” regime in between where there is enough information but where some form of exponential-time search is necessary. I’ll explain the analogy between these problems and spin glass theory in physics, and recent progress toward making this analogy rigorous.

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, École Normale Superieure de Lyon, Northeastern University, the University of Michigan, and Microsoft Research. He has written 160 papers at the boundary between mathematics, physics, and computer science, ranging from quantum computing, social networks, and phase transitions in NP-complete problems and Bayesian inference, to risk assessment in criminal justice. 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.

--------------------

Additional Event: Don't miss Professor Cristopher Moore's key address as our Ida Beam Distinguished Visiting Professor on:
"Transparency and Fairness in AI for Criminal Justice"

• When: Tuesday, September 8, 6:00 p.m. - 7:00 p.m.

• Where: Biology Building East 101

• Who: Students, alumni, faculty, and the general public are all most welcome!

....more info here!