Regensburg 2019 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

PLV: Plenarvorträge

PLV XIII

PLV XIII: Plenary Talk

Thursday, April 4, 2019, 14:00–14:45, H2

The Physics of Inference and Community Detection — •Cristopher Moore — Santa Fe Institute

There is a deep analogy between statistical inference and statistical physics. Just as a block of iron suddenly loses its magnetic field when it reaches a critical temperature, data can suddenly become impossible to analyze if it becomes too noisy or too incomplete. I'll focus on the case of finding communities in social and biological networks, and the "detectability transition" beyond which we cannot classify nodes better than chance, or even tell whether community structure really exists. We'll see how physics both helps us locate these phase transitions, and gives us optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, and spin glass theory.