Algorithmic Pirogov-Sinai Theory

on YouTube ↗44m

" summary

Paper proves a deterministic FPTAS for the hard‑core partition function and sampling on large finite subsets of Z^d at sufficiently high density (lambda above a d‑dependent threshold), using Pirogov‑Sinai theory to convert configurations into a polymer model, prove convergence of the cluster expansion via the Kotecký‑Preiss condition, and control weights with the dilution trick (iterated expansion and inductive weight computation). Method extends to Potts and Widom‑Rowlinson models and yields efficient exactable weights so the algorithm succeeds.

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 2:58Phase Transition
3. 12:01Energy of a Configuration
4. 14:40Phase Diagram
5. 21:45Choosing the Even Boundary Condition
6. 34:28The Dilution Trick

" related talks

• 34mSampling From the Random Cluster Model at All Temperatures on Random GraphsWill Perkins · Computational Phase Transitions (Simons Institute, 2020)
• 24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin GlassesChris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi · ITCS 2023
• 46mPhase Transitions in Random CSPsNike Sun · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 51mRandom Projections for Probabilistic InferenceStefano Ermon · Uncertainty in Computation 2016
• 57mIt ain't over till it's overPei Wu · Beyond the Boolean Cube 2023
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013