Complexity Dichotomies for Counting Problems
From MaRDI portal
Publication:4599359
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
Cited in
(24)- Exponential time complexity of the complex weighted Boolean \#CSP
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- The complexity of counting edge colorings for simple graphs
- Complexity dichotomies of counting problems
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- Approximability of the complementarily symmetric Holant problems on cubic graphs
- Holographic algorithms on domains of general size
- A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Evaluations of Tutte polynomials of regular graphs
- The computational complexity of Holant problems on 3-regular graphs
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Perfect matchings, rank of connection tensors and graph homomorphisms
- Approximability of the eight-vertex model
- Counting degree-constrained subgraphs and orientations
- Quantaloidal approach to constraint satisfaction
- Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
- Complexity of fixed point counting problems in Boolean networks
- 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
This page was built for publication: Complexity Dichotomies for Counting Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4599359)
