Algorithmic Pirogov-Sinai theory

DOI10.1007/s00440-019-00928-yzbMath1436.82007OpenAlexW2995442611WikidataQ127615864 ScholiaQ127615864MaRDI QIDQ2174663

Guus Regts, Tyler Helmuth, Will Perkins

Publication date: 21 April 2020

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00440-019-00928-y

zbMATH Keywords

approximation algorithmscluster expansionFPTASdiscrete spin systemsPirogov-Sinai theoryapproximate sampling

Mathematics Subject Classification ID

Statistical mechanics of polymers (82D60) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Approximation algorithms (68W25) Statistical mechanics of magnetic materials (82D40) Basic methods in statistical mechanics (82M99)

Related Items (12)

Fast mixing via polymers for random graphs with unbounded degree ⋮ Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence ⋮ Absence of zeros implies strong spatial mixing ⋮ Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Correlation decay and the absence of zeros property of partition functions ⋮ Sampling from the low temperature Potts model through a Markov chain on flows ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs ⋮ Approximation Algorithms for the Random Field Ising Model ⋮ Independent sets in the hypercube revisited ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Efficient algorithms for approximating quantum partition functions

Uses Software

• tutte_bhkk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Representation and poly-time approximation for pressure of \(\mathbb Z^2\) lattice models in the non-uniqueness region
• Computing the permanent of (some) complex matrices
• Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
• Counting in two-spin models on \(d\)-regular graphs
• Combinatorics and complexity of partition functions
• Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
• Computing the partition function for graph homomorphisms with multiplicities
• Sequential cavity method for computing free energy and surface pressure
• On a problem of Spencer
• Cluster expansion for abstract polymer models
• Random generation of combinatorial structures from a uniform distribution
• Approximate counting, uniform generation and rapidly mixing Markov chains
• A unified approach to phase diagrams in field theory and statistical mechanics
• Random cluster dynamics for the Ising model is rapidly mixing
• The Ising partition function: zeros and deterministic approximation
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• The relative complexity of approximate counting problems
• Quasi-polynomial mixing of the 2D stochastic Ising model with ``plus boundary up to criticality
• Modular properties of the hard hexagon model.
• On a conjecture of Sokal concerning roots of the independence polynomial
• Random-cluster dynamics in \(\mathbb {Z}^2\)
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Cluster expansion for abstract polymer models. New bounds from an old approach
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The number of trees
• Counting independent sets up to the tree threshold
• FPTAS for #BIS with Degree Bounds on One Side
• Polynomial-Time Approximation Algorithms for the Ising Model
• Computing the partition function for cliques in a graph
• Slow mixing of glauber dynamics via topological obstructions
• Approximating the Partition Function of the Ferromagnetic Potts Model
• On the hard-hexagon model and the theory of modular functions
• Constant Time Generation of Rooted Trees
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Mixing Times of Critical Two‐Dimensional Potts Models
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Left and right convergence of graphs with bounded degree
• Boundary-connectivity via graph theory
• Phase Coexistence for the Hard-Core Model on ℤ²
• Weighted counting of solutions to sparse systems of equations
• Inapproximability of the independent set polynomial in the complex plane
• Algorithms for #BIS-hard problems on expander graphs
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The Random-Cluster Model
• Rapid mixing of Swendsen–Wang dynamics in two dimensions
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model

This page was built for publication: Algorithmic Pirogov-Sinai theory