Classification of a Class of Counting Problems Using Holographic Reductions
DOI10.1007/978-3-642-02882-3_47zbMATH Open1248.68208OpenAlexW1559830925MaRDI QIDQ5323095FDOQ5323095
Authors: Michael Kowalczyk 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Tensor Geometry
- Dimer problem in statistical mechanics-an exact result
- Title not available (Why is that?)
- The complexity of computing the permanent
- The complexity of partition functions
- Complexity classifications of Boolean constraint satisfaction problems
- On counting homomorphisms to directed acyclic graphs
- The Complexity of Weighted Boolean #CSP
- Holant problems and counting CSP
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Complexity of generalized satisfiability counting problems
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- The complexity of counting in sparse, regular, and planar graphs
- Title not available (Why is that?)
- Duality and Polynomial Testing of Tree Homomorphisms
- A complexity dichotomy for partition functions with mixed signs
- Holographic algorithms: from art to science
- Operations with structures
- On Symmetric Signatures in Holographic Algorithms
- The complexity of choosing an H -colouring (nearly) uniformly at random
Cited In (5)
- On the Complexity of Holant Problems
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Holant problems for 3-regular graphs with complex edge functions
- A complete dichotomy rises from the capture of vanishing signatures
This page was built for publication: Classification of a Class of Counting Problems Using Holographic Reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5323095)
