Deterministic Approximation of the Ising Partition Function
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Proves deterministic approximation by combining Liang/Lee–Yang zeros on the unit circle with Barvinok-style Taylor expansion and the Barvinok + Patel–Raghavendra coefficient compression to get FPTASes for ferromagnetic Ising on bounded‑degree graphs and even hypergraphs when beta∈(0,1) and the field λ is bounded away from 1. Extends Asano contraction and Lee–Yang arguments to uniform hyperedges, matches the antiferromagnetic tree correlation‑decay threshold (Sly–Sun) for hardness, and notes the deterministic runtime blows up as λ→1 (near criticality).
AI-written summary · about
chapters (13)
- 0:00Start
- 0:47Easy Models
- 1:05Curie Temperature
- 7:17Ferromagnetic Regime
- 8:54Many-Body or Higher Order Interactions
- 16:30The Ferromagnetic Easing Model
- 22:21Approximation Algorithm
- 23:14When Is the Taylor Expansion Valid
- 26:18The End Theorem
- 32:12Proof of the Leon Theorem
- 34:01Generalize the Multivariate Case
- 37:11Multivariate Easing Model
- 41:46Contraction Step