Approximating the partition function of planar two-state spin systems
From MaRDI portal
Publication:743131
DOI10.1016/j.jcss.2014.06.007zbMath1401.05279arXiv1208.4987OpenAlexW2032098252MaRDI QIDQ743131
Leslie Ann Goldberg, Colin McQuillan, Mark R. Jerrum
Publication date: 22 September 2014
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1208.4987
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, Zero-free regions of partition functions with applications to algorithms and graph limits
Cites Work
- Random generation of combinatorial structures from a uniform distribution
- Some observations on the probabilistic algorithms and NP-hard problems
- Some simplified NP-complete graph problems
- Correlation inequalities on some partially ordered sets
- A partial k-arboretum of graphs with bounded treewidth
- Percolation and the hard-core lattice gas model
- Improved mixing condition on the grid for counting and sampling independent sets
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
- Boundary-to-Boundary Flows in Planar Graphs
- Improved inapproximability results for counting independent sets in the hard-core model
- Counting independent sets up to the tree threshold
- Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities
- Polynomial-Time Approximation Algorithms for the Ising Model
- Slow mixing of glauber dynamics via topological obstructions
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Applications of a Planar Separator Theorem
- Approximation algorithms for NP-complete problems on planar graphs
- The computational complexity of two‐state spin systems
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Correlation Decay up to Uniqueness in Spin Systems
