The Complexity of Approximately Counting in 2-spin Systems on k-uniform Bounded-degree Hypergraphs
summary
Classifies complexity for symmetric Boolean k-ary constraints on k‑uniform bounded‑degree hypergraphs: any nontrivial function has a degree Delta beyond which approximating the partition function becomes intractable (hard even to exponential factors), while trivial functions are easy. Proofs combine reductions to graph independent set (hardness at Delta≥6), gadget constructions, and analysis of uniqueness versus strong spatial mixing on the infinite Delta‑regular tree, supplemented by Mathematica fixed‑point checks; several small‑Delta cases (e.g. hypergraph independent set Δ=4,5) remain open.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 0:33Phase Transitions
- 1:29Configurations
- 3:10Examples
- 3:48Example
- 5:22Anti ferromagnetic regime
- 6:01Avoid trivialities
- 7:15Finite graph
- 7:50Gibbs measure
- 9:13Infinite Delta Regular Tree
- 14:27Uniqueness
- 27:43Strong Independent Sets
- 31:03Strong Spatial Mixing
- 36:18What we know
- 39:56Constraint satisfaction
- 41:14Conservative case
- 42:17Decision problem
- 43:10Constraints