Classification of a Class of Counting Problems Using Holographic Reductions

DOI10.1007/978-3-642-02882-3_47zbMath1248.68208OpenAlexW1559830925MaRDI QIDQ5323095

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

zbMATH Keywords

interpolationholographic algorithmsholographic reductionFibonacci gates

Mathematics Subject Classification ID

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