A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

DOI10.4230/LIPICS.ITCS.2018.2MaRDI QIDQ4993265zbMATH OpenOpenAlexFDO

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

Publication date 15 June 2021

Full work available at URL https://doi.org/10.4230/LIPIcs.ITCS.2018.2

zbMATH Keywords

characterscyclotomic fieldsholant problemsnumber theoryspin systems

Mathematics Subject Classification ID

Miscellaneous applications of number theory (11Z05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• A complexity classification of spin systems with an external field
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• The complexity of quantum spin systems on a two-dimensional square lattice
• The computational complexity of two‐state spin systems
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The complexity of translationally invariant spin chains with low local dimension
• Complexity of Ising polynomials
• The complexity of translationally invariant low-dimensional spin lattices in 3D

Cites work

• A dichotomy for real weighted Holant problems
• A New Holant Dichotomy Inspired by Quantum Computation
• Character coordinates and annihilators of cyclotomic numbers
• Complexity of counting CSP with complex weights
• Dimer problem in statistical mechanics-an exact result
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Holant problems for 3-regular graphs with complex edge functions
• Holographic algorithm with matchgates is universal for planar \#CSP over Boolean domain
• Holographic Algorithms
• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 3760283 (Why is no real title available?)
• scientific article; zbMATH DE number 3485900 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 7204481 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• scientific article; zbMATH DE number 3353353 (Why is no real title available?)
• Matchgates revisited
• On a question of S. Chowla
• On the Structure of Polynomial Time Reducibility
• Spin systems on k-regular graphs with complex edge functions
• The complexity of complex weighted Boolean \#CSP
• The complexity of the counting constraint satisfaction problem
• The Complexity of Weighted Boolean #CSP
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• The nonexistence of nontrivial linear relations between the roots of a certain irreducible equation
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Über die Hauptordnung der ganzen Elemente eines abelschen Zahlkörpers.

Cited in

(1)

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

This page was built for publication: A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

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