The complexity of partition functions

DOI10.1007/978-3-540-27836-8_27MaRDI QIDQ5466470zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov, Martin Grohe

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

zbMATH Keywords

constraint satisfactioncounting complexitygraph homomorphismpartition function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical equilibrium statistical mechanics (general) (82B05)

Recommendations

• The complexity of partition functions
• A complexity dichotomy for hypergraph partition functions
• scientific article; zbMATH DE number 1445311
• scientific article; zbMATH DE number 1545676
• A Complexity Dichotomy for Partition Functions with Mixed Signs

Cited in

(26)

• Complexity classification of the six-vertex model
• Zero-free regions of partition functions with applications to algorithms and graph limits
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Classical simulation of quantum circuits by half Gauss sums
• The complexity of partition functions
• A dichotomy for real weighted Holant problems
• The complexity of approximately counting tree homomorphisms
• A complexity classification of spin systems with an external field
• Progress in complexity of counting problems
• Counting homomorphisms and partition functions
• Computations of the partition function
• scientific article; zbMATH DE number 6341750 (Why is no real title available?)
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• On tractable exponential sums
• The complexity of complex weighted Boolean \#CSP
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• The unbiased black-box complexity of partition is polynomial
• Counting partitions of graphs
• scientific article; zbMATH DE number 1445311 (Why is no real title available?)
• Combinatorics and complexity of partition functions
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• A computational framework for the study of partition functions and graph polynomials
• Perfect matchings, rank of connection tensors and graph homomorphisms
• A complexity dichotomy for hypergraph partition functions
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Computing the partition function for graph homomorphisms with multiplicities

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 Q5466470)