The complexity of the counting constraint satisfaction problem
From MaRDI portal
Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Recommendations
Cited in
(74)- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- The complexity of counting \(\mathrm{CSP}^d\)
- Zero-freeness and approximation of real Boolean Holant problems
- Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
- Dismantlability, connectedness, and mixing in relational structures
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- Counting solutions to CSP using generating polynomials
- A dichotomy for real weighted Holant problems
- Tractability in constraint satisfaction problems: a survey
- A complete dichotomy rises from the capture of vanishing signatures
- The complexity of counting locally maximal satisfying assignments of Boolean CSPs
- An effective dichotomy for the counting constraint satisfaction problem
- On the complexity of \#CSP
- The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
- Counting 4 4 matrix partitions of graphs
- Counting homomorphisms via hypergraph-based structural restrictions
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Organization mechanism and counting algorithm on vertex-cover solutions
- Constraint Satisfaction with Countable Homogeneous Templates
- The Complexity of the Counting Constraint Satisfaction Problem
- Complexity of the counting constraint satisfaction problem
- Enumerating homomorphisms
- The complexity of Boolean Holant problems with nonnegative weights
- Counting constraint satisfaction problems
- Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
- Boolean max-co-clones
- A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Counting constraint satisfaction problems
- Consistency for counting quantifiers
- Counting problems in parameterized complexity
- Approximate Counting CSP Seen from the Other Side
- Uniform Reliability of Self-Join-Free Conjunctive Queries
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- Approximability of the eight-vertex model
- Constant-query testability of assignments to constraint satisfaction problems
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- Computer Science Logic
- Learnability of solutions to conjunctive queries
- Enumerating homomorphisms
- Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
- A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
- Lifted Reasoning for Combinatorial Counting
- Perfect matchings, rank of connection tensors and graph homomorphisms
- Dichotomy result on 3-regular bipartite non-negative functions
- Dichotomy result on 3-regular bipartite non-negative functions
- Approximability of the complementarily symmetric Holant problems on cubic graphs
- A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
- Complexity classification of the eight-vertex model
- CSP beyond tractable constraint languages
- The computational complexity of Holant problems on 3-regular graphs
- On the role of logical separability in knowledge compilation
- The complexity of counting planar graph homomorphisms of domain size 3
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- Exponential time complexity of the complex weighted Boolean \#CSP
- A complexity trichotomy for k-regular asymmetric spin systems with complex edge functions
- Finite algebras with Hom-sets of polynomial size
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- From holant to quantum entanglement and back
- Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
- A characterization of efficiently compilable constraint languages
- Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
- Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
- The complexity of counting homomorphisms seen from the other side
- On the complexity of \#CSP\(^d\)
- Uniform reliability of self-join-free conjunctive queries
- Symmetries and complexity (invited talk)
- On counting (quantum-)graph homomorphisms in finite fields of prime order
- Modular counting CSP: reductions and algorithms
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
This page was built for publication: The complexity of the counting constraint satisfaction problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395730)
