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

3,071 views · Published 3 July 2016 · 1:08:59 · Indexed 30 October 2026

Channel: International Centre for Theoretical Sciences · 2016 · Science & Technology

Watch on YouTube

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

More from this channel