Classification of a Class of Counting Problems Using Holographic Reductions
From MaRDI portal
Publication:5323095
DOI10.1007/978-3-642-02882-3_47zbMath1248.68208OpenAlexW1559830925MaRDI QIDQ5323095
Publication date: 23 July 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02882-3_47
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Holant problems for 3-regular graphs with complex edge functions, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, On the Complexity of Holant Problems, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Complexity of generalized satisfiability counting problems
- The complexity of partition functions
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- The statistics of dimers on a lattice
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Reflection positivity, rank connectivity, and homomorphism of graphs
- On counting homomorphisms to directed acyclic graphs
- The complexity of choosing an H -colouring (nearly) uniformly at random
- On Symmetric Signatures in Holographic Algorithms
- The Complexity of Weighted Boolean #CSP
- Tensor Geometry
- Duality and Polynomial Testing of Tree Homomorphisms
- Holant problems and counting CSP
- Dimer problem in statistical mechanics-an exact result
- Operations with structures
