The complexity of approximating the complex-valued Potts model

DOI10.1007/s00037-021-00218-xOpenAlexW3021148778MaRDI QIDQ2125077

Leslie Ann Goldberg, Andrés Herrera-Poyatos, Andreas Galanis

Publication date: 12 April 2022

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.01076

zbMATH Keywords

Ising modelPotts modelTutte polynomialapproximate countingcounting complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Approximating the chromatic polynomial is as hard as computing it exactly ⋮ The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorics and complexity of partition functions
• Inapproximability of the Tutte polynomial
• A spanning tree expansion of the Jones polynomial
• Computing in the field of complex algebraic numbers
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The Ising partition function: zeros and deterministic approximation
• On the chromatic roots of generalized theta graphs
• Inapproximability of the Tutte polynomial of a planar graph
• On a conjecture of Sokal concerning roots of the independence polynomial
• Theory of monomer-dimer systems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Polynomial-Time Approximation Algorithms for the Ising Model
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• Graph Classes: A Survey
• A Zero-Free Interval for Chromatic Polynomials of Graphs
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• On the computational complexity of the Jones and Tutte polynomials
• Introduction to Dynamical Systems
• The Complexity of Approximating the Matching Polynomial in the Complex Plane
• The Complexity of Computing the Sign of the Tutte Polynomial
• Inapproximability of the Independent Set Polynomial in the Complex Plane
• Classical algorithms, correlation decay, and complex zeros of partition functions of Quantum many-body systems
• Zeros of ferromagnetic 2-spin systems
• Fisher zeros and correlation decay in the Ising model
• Approximating Pairwise Correlations in the Ising Model
• Weighted counting of solutions to sparse systems of equations
• Zeros of Holant problems: locations and algorithms
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Approximate Counting and Quantum Computation
• STATISTICAL MECHANICS OF EQUILIBRIUM AND NONEQUILIBRIUM PHASE TRANSITIONS: THE YANG–LEE FORMALISM
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation

This page was built for publication: The complexity of approximating the complex-valued Potts model