A Complexity Dichotomy for Partition Functions with Mixed Signs
From MaRDI portal
Publication:5390598
DOI10.1137/090757496zbMath1298.68099OpenAlexW2092436554MaRDI QIDQ5390598
Marc Thurley, Leslie Ann Goldberg, Martin Grohe, Mark R. Jerrum
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1821/
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ Counting Homomorphisms to Square-Free Graphs, Modulo 2 ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Complexity of Ising Polynomials ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ The complexity of complex weighted Boolean \#CSP ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ A dichotomy for bounded degree graph homomorphisms with nonnegative weights ⋮ Complexity classification of the eight-vertex model ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ On the Complexity of Holant Problems ⋮ Counting Constraint Satisfaction Problems. ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ The Ising partition function: zeros and deterministic approximation ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Unnamed Item ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ The complexity of counting homomorphisms to cactus graphs modulo 2 ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ The complexity of counting \(\mathrm{CSP}^d\) ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ Classical simulation of quantum circuits by half Gauss sums ⋮ A dichotomy for real weighted Holant problems
This page was built for publication: A Complexity Dichotomy for Partition Functions with Mixed Signs
