Classification of a Class of Counting Problems Using Holographic Reductions

DOI10.1007/978-3-642-02882-3_47MaRDI QIDQ5323095zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Holographic reduction, interpolation and hardness
• Holographic reduction for some counting problems
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems

Cites work

• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A complexity dichotomy for partition functions with mixed signs
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Dimer problem in statistical mechanics-an exact result
• Duality and Polynomial Testing of Tree Homomorphisms
• Holant problems and counting CSP
• Holographic algorithms: from art to science
• On Symmetric Signatures in Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• Operations with structures
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Tensor Geometry
• The Complexity of Weighted Boolean #CSP
• The complexity of choosing an H -colouring (nearly) uniformly at random
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The complexity of partition functions
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Towards a dichotomy theorem for the counting constraint satisfaction problem

Cited in

(5)

• A complete dichotomy rises from the capture of vanishing signatures
• Holant problems for 3-regular graphs with complex edge functions
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• On the Complexity of Holant Problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems

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)