Complexity Dichotomies for Counting Problems
DOI10.1017/9781107477063OpenAlexW2979591888MaRDI QIDQ4599359FDOQ4599359
Authors: Jin-Yi Cai, Xi Chen 
Publication date: 2 January 2018
Full work available at URL: https://doi.org/10.1017/9781107477063
Recommendations
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)
Cited In (24)
- Counting degree-constrained subgraphs and orientations
- Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- Complexity dichotomies of counting problems
- The complexity of counting edge colorings for simple graphs
- Exponential time complexity of the complex weighted Boolean \#CSP
- Complexity of fixed point counting problems in Boolean networks
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Perfect matchings, rank of connection tensors and graph homomorphisms
- Holographic algorithms on domains of general size
- Approximability of the eight-vertex model
- A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- The computational complexity of Holant problems on 3-regular graphs
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over 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
- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- Evaluations of Tutte polynomials of regular graphs
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Quantaloidal approach to constraint satisfaction
- Approximability of the complementarily symmetric Holant problems on cubic graphs
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)
