The complexity of partition functions
From MaRDI portal
Publication:2581263
Recommendations
Cites work
- Closure properties of constraints
- Complexity of generalized satisfiability counting problems
- Duality and Polynomial Testing of Tree Homomorphisms
- Geometric algorithms and combinatorial optimization.
- scientific article; zbMATH DE number 52121 (Why is no real title available?)
- scientific article; zbMATH DE number 2019624 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- On the complexity of H-coloring
- On the computational complexity of the Jones and Tutte polynomials
- The complexity of choosing an H -colouring (nearly) uniformly at random
- The complexity of satisfiability problems
- The computational complexity of two‐state spin systems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Towards a dichotomy theorem for the counting constraint satisfaction problem
Cited in
(82)- Complexity classification of the six-vertex model
- Counting and sampling \(H\)-colourings
- Holographic reduction, interpolation and hardness
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- A finite-tame-wild trichotomy theorem for tensor diagrams
- Lee-Yang theorems and the complexity of computing averages
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- A dichotomy for real weighted Holant problems
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- A complete dichotomy rises from the capture of vanishing signatures
- The complexity of counting homomorphisms to cactus graphs modulo 2
- Complexity of Ising polynomials
- Some algorithmic applications of partition functions in combinatorics
- A complexity classification of spin systems with an external field
- Progress in complexity of counting problems
- A graph integral formulation of the circuit partition polynomial
- Counting homomorphisms and partition functions
- Computations of the partition function
- 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
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- scientific article; zbMATH DE number 6341750 (Why is no real title available?)
- Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
- On tractable exponential sums
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- Enumerating homomorphisms
- scientific article; zbMATH DE number 2019624 (Why is no real title available?)
- Complexity and approximability of the cover polynomial
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- The complexity of Boolean Holant problems with nonnegative weights
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- The unbiased black-box complexity of partition is polynomial
- On the exact learnability of graph parameters: the case of partition functions
- Counting partitions of graphs
- Complexity dichotomy for counting problems
- scientific article; zbMATH DE number 1445311 (Why is no real title available?)
- Computing the Tutte polynomial of lattice path matroids using determinantal circuits
- Counting constraint satisfaction problems
- Counting homomorphisms to trees modulo a prime
- Counting problems in parameterized complexity
- On the counting complexity of mathematical nanosciences
- The worm process for the Ising model is rapidly mixing
- Fast algorithms for general spin systems on bipartite expanders
- Counting homomorphisms modulo a prime number
- Combinatorics and complexity of partition functions
- Classification of a Class of Counting Problems Using Holographic Reductions
- A computational proof of complexity of some restricted counting problems
- Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
- A complexity dichotomy for partition functions with mixed signs
- Automata, Languages and Programming
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- A computational framework for the study of partition functions and graph polynomials
- Approximate counting via correlation decay in spin systems
- Complexity classification of the eight-vertex model
- The computational complexity of Holant problems on 3-regular graphs
- A complexity dichotomy for hypergraph partition functions
- The complexity of counting planar graph homomorphisms of domain size 3
- A complexity trichotomy for k-regular asymmetric spin systems with complex edge functions
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- On the complexity of generalized chromatic polynomials
- Computing the partition function for graph homomorphisms
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- From holant to quantum entanglement and back
- Meta-theorems for graph polynomials
- Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
- Two-state spin systems with negative interactions
- Spin systems on k-regular graphs with complex edge functions
- Two-state spin systems with negative interactions
- Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
- Bounded degree nonnegative counting CSP
- Symmetries and complexity (invited talk)
- On counting (quantum-)graph homomorphisms in finite fields of prime order
- Modular counting CSP: reductions and algorithms
- P-time algorithms for typical \#EO problems
- The complexity of weighted Boolean \#CSP with mixed signs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Computing the partition function for graph homomorphisms with multiplicities
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
- An approximation trichotomy for Boolean \#CSP
This page was built for publication: The complexity of partition functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581263)
