Approximating 2-State Spin Systems
summary
Survey of which 2‑state spin parameters are approximable versus hard with concrete claims and tools For antiferromagnetic cases there is a near‑complete classification via correlation decay and tree uniqueness and for ferromagnetic cases the talk proves a new conditional strong spatial mixing result on trees that yields FPTAS under explicit bounds on λ and β using the self-avoiding walk tree and telescoping product recursions It gives reductions and a bisection technique showing #P-hardness for most complex parameter choices and lists open gaps between uniqueness and efficient algorithms
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:30Easing Model
- 2:36Recap
- 3:42Examples
- 5:40Antiferromagnetic
- 9:04Lambda
- 13:52Selfevolving Work Trees
- 18:44Uniqueness
- 20:30Generalizing
- 25:49Conditional Special Mixing
- 33:15Complex Easy Model
- 39:05Proof
- 40:33Open Questions
related talks
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
26mTight Algorithmic Thresholds for Spin Glass Hamiltonians
01h 18mStatistical Physics and Computation in High Dimension
01h 11mStatistical Physics and Computation in High Dimension
33mOptimization of Full-RSB Spherical Spin Glasses
44mAlgorithmic Pirogov-Sinai Theory
01h 06mArea Laws and Topological Order in a Many-body Localized State
59mOptimizing Noncommutative Polynomials: The SYK Model