Pedagogical Talk: Random Optimisation Problems

on YouTube ↗01h 17m

" summary

Examines max‑cut on a random d‑regular graph and shows the usual first‑moment estimate matches the free energy only up to a specific inverse‑temperature threshold β; above β the system exhibits replica‑symmetry breaking so the first‑moment bound is loose. Uses the planted model plus spatial‑mixing/non‑reconstruction on the broadcast tree to justify a truncated second‑moment and lower bound, then compares free energies to prove a phase transition. Provides concrete bounds for small d (e.g. d=3 cutoff ≈0.95 of edges) and an explicit variational formula for large d.

AI-written summary · about

" chapters (12)

1. 0:00Start
2. 2:09What are random optimisation problems?
3. 3:12The average case myth
4. 11:39The probabilistic method
5. 14:35A glimpse of complexity?
6. 16:43Part 2
7. 17:28Running example
8. 18:48Combinatorial bounds
9. 22:52The physics perspective
10. 48:04The replica symmetry breaking transition
11. 49:15First attempt
12. 57:57The planted model diverges

" related talks

• 49mExtremal Cuts of Sparse Random GraphsAmir Dembo · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 18mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 52mCounting Solutions to Random Constraint Satisfaction ProblemsAllan Sly · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 31mGraphons and Graph Limits 2Christian Borgs · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 35mOn the Chromatic Number of Random Regular GraphsSamuel Hetterich · Random Instances and Phase Transitions (Simons Institute, 2016)
• 43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional ClustCris Moore · Random Instances and Phase Transitions (Simons Institute, 2016)
• 46mPhase Transitions in Random CSPsNike Sun · Random Instances and Phase Transitions (Simons Institute, 2016)