Computational Complexity of Holant Problems
From MaRDI portal
Publication:3096095
DOI10.1137/100814585zbMath1234.68130OpenAlexW2003722559MaRDI QIDQ3096095
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Publication date: 7 November 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/24a9608fd20ceb367cf8a45bb18fd7892a69847b
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Zero-freeness and approximation of real Boolean Holant problems ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Graph parameters from symplectic group invariants ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Holographic reduction, interpolation and hardness ⋮ The complexity of complex weighted Boolean \#CSP ⋮ Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Beyond windability: approximability of the four-vertex model ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ Complexity classification of the six-vertex model ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP ⋮ On the Complexity of Holant Problems ⋮ On the complexity of generalized chromatic polynomials ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Unnamed Item ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ Clifford gates in the Holant framework ⋮ Mixed partition functions and exponentially bounded edge-connection rank ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
This page was built for publication: Computational Complexity of Holant Problems
