Complexity, Phase Transitions, and Inference by Cristopher Moore (part 1)

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 problems like community detection in networks, and clustering of sparse high-dimensional data, where if our data becomes too sparse or too noisy it becomes impossible to find the underlying pattern; moreover, I will discuss optimal algorithms that succeed as well as possible up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory. This lecture is part of Games, Epidemics and Behavior Table of Contents (powered by https://videoken.com) 0:00:00 ICTS 0:00:04 CENTRE for 0:00:11 Christopher Moore, Santa Fe Institute 0:01:18 Statistical inference statistical physics 0:05:20 Why least squares? 0:06:26 A model of noise 0:08:12 From probability to energy 0:09:11 Changing the model 0:11:59 Uncertainty, equilibrium, and the energy landscape 0:16:03 The Ising model of magnetism 0:21:10 Bumpy landscapes 0:24:09 Divided we blog 0:24:49 Who eats whom 0:25:23 I record that I was born on a Friday 0:25:56 The stochastic block model 0:29:09 Likelihood and energy 0:33:35 Overfitting 0:35:27 Information in the block model: the effect of a link 0:39:14 Detectability thresholds 0:45:28 Clustering high-dimensional data 0:48:17 Techniques 0:52:39 A little light reading 0:53:15 Detectability thresholds