Polynomial-time approximation algorithms for the Ising model (extended abstract)

DOI10.1007/BFB0032051MaRDI QIDQ4038711zbMATH OpenFDO

Authors Alistair Sinclair, Mark Jerrum

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0032051

zbMATH Keywords

ferromagnetic Ising systeminteraction graphIsing modelMarkov chainpolynomial-time approximation algorithms

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Probabilistic methods, stochastic differential equations (65C99) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Review text

[For the entire collection see Zbl 0758.00017.] In Section 2 we describe the transformation of the Ising model to the new domain in which configurations are spanning subgraphs of the interaction graph. Section 4 is devoted to a discussion of the Markov chain on these configurations, and in particular to a proof that it is rapidly mixing. This fact is used in Section 3 to construct a fpras for the partition function of an arbitrary ferromagnetic Ising system, and in Section 5 to construct efficient approximation algorithms for the mean energy and the mean magnetic moment. Also in Section 3 we present strong evidence that our results are, in a precise theoretical sense, best possible. For the purposes of this abstract, we omit most of the proofs and technical details and concentrate on outlining the main ideas: the interested reader is referred to the full paper (submitted to Journal of the ACM).

Recommendations

• Polynomial-Time Approximation Algorithms for the Ising Model
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
• Stratified sampling for the Ising model: A graph-theoretic approach
• The Ising partition function: zeros and deterministic approximation

Cited in

(21)

• Polynomial-time algorithm for simulation of weakly interacting quantum Spin systems
• Approximability of the ground state problem for certain Ising spin glasses
• Computational complexity of loss networks
• The Ising partition function: zeros and deterministic approximation
• On the number of Eulerian orientations of a graph
• Poisson approximations for the Ising model
• Stratified sampling for the Ising model: A graph-theoretic approach
• Polynomial-Time Approximation Algorithms for the Ising Model
• A novel approach to Ising problems
• Simulation reduction of the Ising model to general matchings
• The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Cycle basis Markov chains for the Ising model
• Approximating pairwise correlations in the Ising model
• Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
• An accelerated exhaustive enumeration algorithm in the Ising model
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
• Optimal sufficient requirements on the embedded Ising problem in polynomial time
• Computational thresholds for the fixed-magnetization Ising model
• A binomial approximation method for the Ising model
• Ising models on locally tree-like graphs

This page was built for publication: Polynomial-time approximation algorithms for the Ising model (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038711)