On the Complexity of Holant Problems
From MaRDI portal
Cites work
- A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- A computational proof of complexity of some restricted counting problems
- A dichotomy for real weighted Holant problems
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A simple FPTAS for counting edge covers
- Approximating the Permanent
- Canonical Paths for MCMC: from Art to Science
- Classification of a Class of Counting Problems Using Holographic Reductions
- Complexity classifications of Boolean constraint satisfaction problems
- Complexity of generalized satisfiability counting problems
- Computational complexity of Holant problems
- Dichotomy for Holant* problems of Boolean domain
- Dichotomy for Holant* problems with a function on domain size 3
- Dimer problem in statistical mechanics-an exact result
- Even delta-matroids and the complexity of planar Boolean CSPs
- Expressiveness of matchgates.
- Fanout limitations on constraint systems
- FPTAS for counting weighted edge covers
- FPTAS for weighted Fibonacci gates and its applications
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- General factors of graphs
- Holant problems and counting CSP
- Holant problems for regular graphs with complex edge functions
- Holographic Algorithms
- Holographic algorithms by Fibonacci gates
- Holographic algorithms: from art to science
- Holographic reduction, interpolation and hardness
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2003
- Maximum matching and a polyhedron with 0,1-vertices
- On counting homomorphisms to directed acyclic graphs
- On Planar Boolean CSP
- On the Structure of Polynomial Time Reducibility
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- Paths, Trees, and Flowers
- Polynomial-Time Approximation Algorithms for the Ising Model
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Spin systems on k-regular graphs with complex edge functions
- Tensor Geometry
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- The complexity of complex weighted Boolean \#CSP
- The complexity of computing the permanent
- The Complexity of Enumeration and Reliability Problems
- The complexity of satisfiability problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The linear delta-matroid parity problem
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
Cited in
(6)- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations
- scientific article; zbMATH DE number 7204481 (Why is no real title available?)
- The HOM Problem is EXPTIME-Complete
- AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
- Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
This page was built for publication: On the Complexity of Holant Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993599)
