The Complexity of Symmetric Boolean Parity Holant Problems
From MaRDI portal
Publication:5891075
DOI10.1137/100815530zbMath1286.68232OpenAlexW2000217912MaRDI QIDQ5891075
Heng Guo, Pinyan Lu, Leslie G. Valiant
Publication date: 4 July 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100815530
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (13)
Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ The complexity of counting homomorphisms to cactus graphs modulo 2 ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints ⋮ A dichotomy for real weighted Holant problems
This page was built for publication: The Complexity of Symmetric Boolean Parity Holant Problems
