Polynomial-Time Approximation Algorithms for the Ising Model
From MaRDI portal
Markov chainMonte Carlo simulationIsing modelpartition functionpolynomial-time approximation algorithmsrapid mixingIsing spin configurationsferromagnetic Ising system
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Analysis of algorithms and problem complexity (68Q25) 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)
Recommendations
- scientific article; zbMATH DE number 177833
- scientific article; zbMATH DE number 1305519
- 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
(only showing first 100 items - show all)- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Glauber dynamics for Ising model on convergent dense graph sequences
- NEW ALGORITHM FOR THE COMPUTATION OF THE PARTITION FUNCTION FOR THE ISING MODEL ON A SQUARE LATTICE
- Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Counting hypergraph colorings in the local lemma regime
- Gauging variational inference
- A graph polynomial for independent sets of bipartite graphs
- Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
- Randomized scheduling algorithm for queueing networks
- The Ising partition function: zeros and deterministic approximation
- Toward derandomizing Markov chain Monte Carlo
- Rapid mixing of Swendsen-Wang dynamics in two dimensions
- Approximately counting paths and cycles in a graph
- The Tutte-Potts connection in the presence of an external magnetic field
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- Zeros and approximations of holant polynomials on the complex plane
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Bucket renormalization for approximate inference
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Computing elastic moduli of two-dimensional random networks of rigid and nonrigid bonds by simulated annealing
- Counting over non-planar graphs
- Sparse reliable graph backbones
- Approximating pairwise correlations in the Ising model
- Cycle basis Markov chains for the Ising model
- A new approach to solving three combinatorial enumeration problems on planar graphs
- On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
- Tractable minor-free generalization of planar zero-field Ising models
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
- On the Complexity of Holant Problems
- Inapproximability of the Tutte polynomial
- On the hardness of sampling independent sets beyond the tree threshold
- Simulation reduction of the Ising model to general matchings
- The complexity of approximating the complex-valued Potts model
- Combinatorial bandits
- Approximating the partition function of planar two-state spin systems
- Approximately counting independent sets of a given size in bounded-degree graphs
- Counting problems in parameterized complexity
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- An accelerated exhaustive enumeration algorithm in the Ising model
- Spectral independence via stability and applications to Holant-type problems
- Some problems on approximate counting in graphs and matroids
- Approximating the number of monomer-dimer coverings of a lattice.
- Robust exponential memory in Hopfield networks
- More on zeros and approximation of the Ising partition function
- Spectral bounds for the Ising ferromagnet on an arbitrary given graph
- Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
- Faster mixing and small bottlenecks
- Approximate counting for spin systems in sub-quadratic time
- Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2
- Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures
- Smoothed counting of 0–1 points in polyhedra
- A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
- Critical Ising on the square lattice mixes in polynomial time
- On the two-dimensional dynamical Ising model in the phase coexistence region
- scientific article; zbMATH DE number 177833 (Why is no real title available?)
- Complexity of Ising polynomials
- Inverse sampling for nonasymptotic sequential estimation of bounded variable means
- Approximation algorithms for the normalizing constant of Gibbs distributions
- Convergence rates of Markov chains for some self-assembly and non-saturated Ising models
- Mean-field Potts and random-cluster dynamics from high-entropy initializations
- Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration
- Zero-freeness and approximation of real Boolean Holant problems
- The computational complexity of estimating MCMC convergence time
- Computational thresholds for the fixed-magnetization Ising model
- scientific article; zbMATH DE number 7375995 (Why is no real title available?)
- Fixed Precision MCMC Estimation by Median of Products of Averages
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
- A complexity classification of spin systems with an external field
- A binomial approximation method for the Ising model
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Kernelization for counting problems on graphs: preserving the number of minimum solutions
- Stratified sampling for the Ising model: A graph-theoretic approach
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- Fast relaxation of the random field Ising dynamics
- The computational complexity of generating random fractals
- Universality of the mean-field for the Potts model
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- scientific article; zbMATH DE number 7378644 (Why is no real title available?)
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Approximation Algorithms for the Random Field Ising Model
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- Low-temperature Ising dynamics with random initializations
- scientific article; zbMATH DE number 1563189 (Why is no real title available?)
- Approximate counting via correlation decay in spin systems
- Counting constraint satisfaction problems
- A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
- Classical restrictions of generic matrix product states are quasi-locally Gibbsian
- Optimal sufficient requirements on the embedded Ising problem in polynomial time
- On the two-dimensional stochastic Ising model in the phase coexistence region near the critical point
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- Low depth quantum circuits for Ising models
- The complexity of approximating the complex-valued Potts model
- Geometric bounds on the fastest mixing Markov chain
This page was built for publication: Polynomial-Time Approximation Algorithms for the Ising Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3142597)
