Decay of Correlations in Spin Systems

on YouTube ↗01h 03m

" summary

Shows that the algorithmic phase transition aligns with the uniqueness threshold on the infinite (d+1)-regular tree and gives a concrete route to algorithms: reduce graph marginals to a self-avoiding walk tree, translate ratios to a potential (e.g. potential function log) so the recursion contracts, and obtain strong spatial mixing ⇒ deterministic FPTAS below the threshold. Extends to anti-ferromagnetic two-spin, hypergraph matchings and monomer–dimer; uses Hölder bounds (LP norms) and the connector constant to replace max degree. Leaves hardness gaps at the critical point and for some hypergraph regimes unresolved.

AI-written summary · about

" chapters (12)

1. 0:00Correlation and complexity
2. 2:00Spin models and frameworks
3. 5:31Spatial mixing concepts
4. 9:15Tree recursion methods
5. 12:24Extremal proofs in trees
6. 15:24Hypergraph matching models
7. 24:10Potential method analysis
8. 31:13Generalizing spin models
9. 37:28Primitive spatial mixing
10. 40:54Hardness and conjectures
11. 46:51Refined correlation decay
12. 56:20Discussion and open problems

" related talks

• 55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order LogicBenjamin Rossman · Symmetry, Logic, Computation 2016
• 50mRandom Combinatorial MatricesAmin Coja-Oghlan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 57mReflection Positivity as Complement to the Location of Zeros of Partition FunctionsElliott Lieb · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 01h 05mOn the Critical Point Method and Deciding Connectivity Queries in Real Algebraic SetsMohab Safey El Din · Solving Polynomial Equations (Simons Institute, 2014)
• 29mExtended Formulations and Information ComplexityAnkur Moitra · Information Theory in Complexity Theory and Combinatorics 2015
• 01h 04mInformation Theory in Computational Complexity IJaikumar Radhakrishnan · Information Theory Boot Camp 2015
• 23mA New Connection Between Node and Edge Depth Robust GraphsJeremiah Blocki, Mike Cinkoske · ITCS 2021