From Holant to \#CSP and back: dichotomy for Holant^c problems
From MaRDI portal
Publication:1934313
Recommendations
- From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems
- On the CSP Dichotomy Conjecture
- Holant problems and counting CSP
- On the complexity of \#CSP
- On the Complexity of Holant Problems
- A proof of the CSP dichotomy conjecture
- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- Some new tractable classes of CSPs and their relations with backtracking algorithms
- scientific article; zbMATH DE number 3921977
- The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
Cites work
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- A computational proof of complexity of some restricted counting problems
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Automata, Languages and Programming
- Classification of a Class of Counting Problems Using Holographic Reductions
- Complexity classifications of Boolean constraint satisfaction problems
- Computational complexity of counting problems on 3-regular planar graphs
- Corrigendum: The complexity of counting graph homomorphisms
- Holant problems and counting CSP
- Holant problems for regular graphs with complex edge functions
- Holographic Algorithms
- Holographic algorithms: from art to science
- scientific article; zbMATH DE number 1445311 (Why is no real title available?)
- On Counting Homomorphisms to Directed Acyclic Graphs
- On counting homomorphisms to directed acyclic graphs
- On the complexity of H-coloring
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Tensor Geometry
- The complexity of partition functions
- The Complexity of Weighted Boolean #CSP
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Towards a dichotomy theorem for the counting constraint satisfaction problem
Cited in
(31)- Computing and estimating the volume of the solution space of SMT(LA) constraints
- Clifford gates in the Holant framework
- Holographic reduction, interpolation and hardness
- Holographic reduction for some counting problems
- Parameterized counting of partially injective homomorphisms
- Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
- A dichotomy for real weighted Holant problems
- A complete dichotomy rises from the capture of vanishing signatures
- From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems
- Computational complexity of Holant problems
- The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Holographic reduction: a domain changed application and its partial converse theorems
- Holant clones and the approximability of conservative holant problems
- On the Complexity of Holant Problems
- A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- The complexity of approximating the matching polynomial in the complex plane
- A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
- Holant problems and counting CSP
- Zeros of Holant problems: locations and algorithms
- Classification of a Class of Counting Problems Using Holographic Reductions
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Dichotomy for Holant* problems with a function on domain size 3
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Where Tutte and Holant meet: a view from counting complexity
- Complexity classification of the eight-vertex model
- Spectral independence via stability and applications to Holant-type problems
- Sub-exponential time lower bounds for \#VC and \#Matching on 3-regular graphs
- On the complexity of \#CSP\(^d\)
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
This page was built for publication: From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1934313)
