Unlocking the Secrets of Inference Through Physics 🔍

Cristopher Moore (Santa Fe Institute)
What physics can tell us about inference?

Abstract: 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 two problems of
interest to a broad range of data sciences: community detection in
social and biological networks, and clustering of sparse
high-dimensional data. In both cases, 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. Physics both helps us locate
these 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.


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
Polytechnique, École Normale Superieure du Lyon, 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.


Videos from Ecole Normale Supérieure, visit
Savoirs-ENS (http://savoirs.ens.fr/) for more videos.