Complexity Dichotomies for Counting Problems
From MaRDI portal
(Redirected from Publication:4599359)
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
Cited in
(34)- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- Complexity of fixed point counting problems in Boolean networks
- Evaluations of Tutte polynomials of regular graphs
- Counting degree-constrained subgraphs and orientations
- Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
- The complexity of counting edge colorings for simple graphs
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Complexity dichotomies of counting problems
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- Approximability of the eight-vertex model
- A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Perfect matchings, rank of connection tensors and graph homomorphisms
- 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 complementarily symmetric Holant problems on cubic graphs
- Holographic algorithms on domains of general size
- Quantaloidal approach to constraint satisfaction
- The computational complexity of Holant problems on 3-regular graphs
- Exponential time complexity of the complex weighted Boolean \#CSP
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Counting perfect matchings and the eight-vertex model
- From holant to quantum entanglement and back
- Counting degree-constrained orientations
- Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
- Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
- Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
- Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
- Bounded degree nonnegative counting CSP
- Symmetries and complexity (invited talk)
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)
