"More is Different." Also in Computing?

on YouTube ↗01h 04m

" summary

Argues that statistical‑physics tools (replica/cavity/mean‑field) yield concrete, testable claims: random k‑SAT has a sharp threshold at alpha_c ≈ 4.2667, solutions cluster exponentially above a clustering threshold, and survey propagation exploits that cluster structure to solve many hard instances. Shows LDPC/message‑passing has its own algorithmic threshold below Shannon, and that seeded belief propagation (spatially coupled measurement matrices) pushes compressed‑sensing recovery to the information‑theoretic limit in simulations and experiments. Glassy metastable states explain algorithmic failures.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 0:09Simons symposium on «Visions of the theory of computing Berkeley, May 30, 2013
3. 14:41Intermediate steps Use spin glass concepts and methods to provide a different viewpoint about computation, and to design new algorithms
4. 33:14Infer regulatory interactions among many genes using only a limited number of experimental conditions
5. 39:28For id signals, Bayes reconstruction is in principle optimal, even if the prior is not the correct one.

" related talks

• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 48mLearning by Local Entropy MaximizationRiccardo Zecchina · Random Instances and Phase Transitions (Simons Institute, 2016)
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 01h 31mBig Data: The Computation/Statistics InterfaceMichael Jordan · Big Data Boot Camp 2013