The complexity of partition functions
From MaRDI portal
Publication:2581263
DOI10.1016/j.tcs.2005.09.011zbMath1081.68030OpenAlexW2118223706MaRDI QIDQ2581263
Martin Grohe, Andrei A. Bulatov
Publication date: 9 January 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.011
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (47)
The complexity of weighted Boolean \#CSP with mixed signs ⋮ 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 ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Holographic reduction, interpolation and hardness ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ Computing the partition function for graph homomorphisms with multiplicities ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ A dichotomy for bounded degree graph homomorphisms with nonnegative weights ⋮ A finite-tame-wild trichotomy theorem for tensor diagrams ⋮ Complexity classification of the eight-vertex model ⋮ Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Enumerating homomorphisms ⋮ A complexity classification of spin systems with an external field ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Unnamed Item ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ Complexity and approximability of the cover polynomial ⋮ Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs ⋮ Counting Constraint Satisfaction Problems. ⋮ Computing the Tutte polynomial of lattice path matroids using determinantal circuits ⋮ The worm process for the Ising model is rapidly mixing ⋮ On the complexity of generalized chromatic polynomials ⋮ Computing the partition function for graph homomorphisms ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ A computational proof of complexity of some restricted counting problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ An approximation trichotomy for Boolean \#CSP ⋮ Unnamed Item ⋮ 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 ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ A dichotomy for real weighted Holant problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- On the complexity of H-coloring
- Geometric algorithms and combinatorial optimization.
- Complexity of generalized satisfiability counting problems
- The complexity of choosing an H -colouring (nearly) uniformly at random
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- The computational complexity of two‐state spin systems
- On the computational complexity of the Jones and Tutte polynomials
- Duality and Polynomial Testing of Tree Homomorphisms
- The complexity of satisfiability problems
This page was built for publication: The complexity of partition functions
