A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory

DOI10.1007/s00037-023-00237-wOpenAlexW4376874069MaRDI QIDQ6113105

Kurt Girstmair, Zhiguo Fu, Michael Kowalczyk, Jin-Yi Cai

Publication date: 10 July 2023

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

Full work available at URL: https://doi.org/10.1007/s00037-023-00237-w

zbMATH Keywords

characterscyclotomic fieldsspin systemsnumber theoryHolant problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• The complexity of complex weighted Boolean \#CSP
• Spin systems on \(k\)-regular graphs with complex edge functions
• Character coordinates and annihilators of cyclotomic numbers
• The complexity of planar Boolean \#CSP with complex weights
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• The nonexistence of nontrivial linear relations between the roots of a certain irreducible equation
• The statistics of dimers on a lattice
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Complexity of Ferromagnetic Ising with Local Fields
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• On the Structure of Polynomial Time Reducibility
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Complexity of Counting CSP with Complex Weights
• Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Beitrag zur Theorie des Ferromagnetismus
• A New Holant Dichotomy Inspired by Quantum Computation
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Dimer problem in statistical mechanics-an exact result
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• The complexity of the counting constraint satisfaction problem
• On a question of S. Chowla
• Correlation Decay up to Uniqueness in Spin Systems

This page was built for publication: A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory