Spin systems on \(k\)-regular graphs with complex edge functions

DOI10.1016/j.tcs.2012.01.021zbMath1252.68149OpenAlexW2003244973MaRDI QIDQ690458

Jin-Yi Cai, Michael Kowalczyk

Publication date: 27 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.021

zbMATH Keywords

interpolationpartition functioncounting complexityholographic algorithmsdichotomy theoremHolant problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Holant problems for 3-regular graphs with complex edge functions, Holographic reduction, interpolation and hardness, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, Holographic algorithms beyond matchgates, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, On the Complexity of Holant Problems, A collapse theorem for holographic algorithms with matchgates on domain size at most 4, The complexity of planar Boolean \#CSP with complex weights, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A computational proof of complexity of some restricted counting problems
• Holographic algorithms: from art to science
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the complexity of #CSP
• The statistics of dimers on a lattice
• Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities
• Holant Problems for Regular Graphs with Complex Edge Functions
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The Complexity of the Counting Constraint Satisfaction Problem
• Holographic Algorithms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Weighted Boolean #CSP
• Beitrag zur Theorie des Ferromagnetismus
• Holant problems and counting CSP
• Dimer problem in statistical mechanics-an exact result
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The Spontaneous Magnetization of a Two-Dimensional Ising Model
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem