Complexity Dichotomies for Counting Problems
From MaRDI portal
Publication:4599359
DOI10.1017/9781107477063OpenAlexW2979591888MaRDI QIDQ4599359
Publication date: 2 January 2018
Full work available at URL: https://doi.org/10.1017/9781107477063
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (20)
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs ⋮ Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ Counting degree-constrained subgraphs and orientations ⋮ A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation ⋮ A dichotomy for bounded degree graph homomorphisms with nonnegative weights ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ Holographic algorithms on domains of general size ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS ⋮ Unnamed Item ⋮ The complexity of counting edge colorings for simple graphs ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Approximability of the eight-vertex model ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
This page was built for publication: Complexity Dichotomies for Counting Problems
