The Complexity of Symmetric Boolean Parity Holant Problems

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

zbMATH Keywords

complexityparitydichotomy theoremparity Holant problems

Mathematics Subject Classification ID

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