Polynomial-Time Approximation Algorithms for the Ising Model

DOI10.1137/0222066zbMath0782.05076OpenAlexW2024710200WikidataQ60264972 ScholiaQ60264972MaRDI QIDQ3142597

Publication date: 20 December 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/181eba118d1be4a6c90069f9f008712b5e82074a

zbMATH Keywords

partition function Monte Carlo simulation Markov chain Ising model polynomial-time approximation algorithms rapid mixing Ising spin configurations ferromagnetic Ising system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Parallel algorithms in computer science (68W10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

$\#$BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, Approximate computations for binary Markov random fields and their use in Bayesian models, Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration, The complexity of approximating the complex-valued Potts model, Universality of the mean-field for the Potts model, Stein's method for concentration inequalities, QUANTUM WALKS ON NECKLACES AND MIXING, Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, Stratified sampling for the Ising model: A graph-theoretic approach, Zero-freeness and approximation of real Boolean Holant problems, A new approach to solving three combinatorial enumeration problems on planar graphs, A Graph Polynomial for Independent Sets of Bipartite Graphs, Complexity of Ising Polynomials, Random cluster dynamics for the Ising model is rapidly mixing, Mixing of the Glauber dynamics for the ferromagnetic Potts model, Low depth quantum circuits for Ising models, On the two-dimensional dynamical Ising model in the phase coexistence region, Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Faster mixing and small bottlenecks, Fixed Precision MCMC Estimation by Median of Products of Averages, Zeros and approximations of holant polynomials on the complex plane, Algorithmic Pirogov-Sinai theory, Sampling weighted perfect matchings on the square-octagon lattice, Total variation discrepancy of deterministic random walks for ergodic Markov chains, Inverse Sampling for Nonasymptotic Sequential Estimation of Bounded Variable Means, The Complexity of Approximately Counting Tree Homomorphisms, The complexity of approximating complex-valued Ising and Tutte partition functions, Hitting time of quantum walks with perturbation, Cluster analysis of spatial point patterns: posterior distribution of parents inferred from offspring, Sparse reliable graph backbones, Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing, Randomized scheduling algorithm for queueing networks, Unnamed Item, Unnamed Item, A complexity classification of spin systems with an external field, Approximating partition functions of the two-state spin system, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, The computational complexity of generating random fractals, Unnamed Item, Unnamed Item, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Complexity classification of the six-vertex model, Some Problems on Approximate Counting in Graphs and Matroids, Combinatorial bandits, Critical Ising on the square lattice mixes in polynomial time, Unnamed Item, Evolutionary algorithms and dynamic programming, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, On the Complexity of Holant Problems, Counting Constraint Satisfaction Problems., The Ising partition function: zeros and deterministic approximation, Location of zeros for the partition function of the Ising model on bounded degree graphs, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Inapproximability of the Tutte polynomial, Spectral bounds for the Ising ferromagnet on an arbitrary given graph, Algorithms for #BIS-Hard Problems on Expander Graphs, The Potts model and the Tutte polynomial, Analyzing Glauber dynamics by comparison of Markov chains, Estimation in spin glasses: a first step, Classical restrictions of generic matrix product states are quasi-locally Gibbsian, The worm process for the Ising model is rapidly mixing, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Approximately counting paths and cycles in a graph, Perfect Simulation for Image Restoration, An upper bound on the convergence time of the Gibbs sampler in Ising models, Glauber dynamics on trees and hyperbolic graphs, Rapid mixing of Gibbs sampling on graphs that are sparse on average, The Tutte-Potts connection in the presence of an external magnetic field, Robust exponential memory in Hopfield networks, A worm algorithm for the fully-packed loop model, Dichotomy for Holant$^\ast$ problems on the Boolean domain, Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Convergence rates of Markov chains for some self-assembly and non-saturated Ising models, A binomial approximation method for the Ising model, Approximating the partition function of planar two-state spin systems, A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics, On the hardness of sampling independent sets beyond the tree threshold, The Computational Complexity of Estimating MCMC Convergence Time, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Counting Hypergraph Colorings in the Local Lemma Regime, Approximate Counting via Correlation Decay in Spin Systems, On the two-dimensional stochastic Ising model in the phase coexistence region near the critical point, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, More on zeros and approximation of the Ising partition function, Simulation reductions for the Ising model, Rapid mixing of Swendsen–Wang dynamics in two dimensions, A new genetic algorithm, The complexity of approximating the complex-valued Potts model, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Unnamed Item, Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z², Approximating the number of monomer-dimer coverings of a lattice., Approximation algorithms for the normalizing constant of Gibbs distributions, Unnamed Item, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs, Functional clones and expressibility of partition functions, Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction, Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Smoothed counting of 0–1 points in polyhedra, Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, Sampling from the low temperature Potts model through a Markov chain on flows, Commuting quantum circuits and complexity of Ising partition functions, A complexity trichotomy for $k$-regular asymmetric spin systems using number theory, Spatial mixing and the random‐cluster dynamics on lattices, Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, Low-temperature Ising dynamics with random initializations, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Approximation Algorithms for the Random Field Ising Model, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Geometric bounds on the fastest mixing Markov chain, Beyond windability: approximability of the four-vertex model, Counting over non-planar graphs, A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid, Approximately Counting Embeddings into Random Graphs, Gauging variational inference, Bucket renormalization for approximate inference, Efficient algorithms for approximating quantum partition functions, Tractable minor-free generalization of planar zero-field Ising models, Dynamic Sampling from Graphical Models, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs