Spin systems on k-regular graphs with complex edge functions

DOI10.1016/J.TCS.2012.01.021zbMATH Open1252.68149OpenAlexW2003244973MaRDI QIDQ690458FDOQ690458

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Dimer problem in statistical mechanics-an exact result
• The complexity of partition functions
• Complexity classifications of Boolean constraint satisfaction problems
• On the complexity of \#CSP
• Holant Problems for Regular Graphs with Complex Edge Functions
• 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
• A computational proof of complexity of some restricted counting problems
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The Complexity of the Counting Constraint Satisfaction Problem
• 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
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of counting in sparse, regular, and planar graphs
• Computational complexity of counting problems on 3-regular planar graphs
• The Spontaneous Magnetization of a Two-Dimensional Ising Model
• Holographic algorithms: from art to science
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem
• Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities

Cited In (12)

• On the Complexity of Holant Problems
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• 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
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• A complexity trichotomy for \(k\)-regular asymmetric spin systems with complex edge functions
• Holographic algorithms beyond matchgates
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• A complete dichotomy rises from the capture of vanishing signatures
• Holographic reduction, interpolation and hardness
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• The complexity of planar Boolean \#CSP with complex weights

This page was built for publication: Spin systems on \(k\)-regular graphs with complex edge functions

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