The complexity of symmetric Boolean parity Holant problems

DOI10.1137/100815530MaRDI QIDQ5891075zbMATH OpenOpenAlexFDO

Authors 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

complexitydichotomy theoremparityparity Holant problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• Computational complexity of Holant problems
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Dichotomy for Holant* problems of Boolean domain
• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)

Cited in

(18)

• On blockwise symmetric matchgate signatures and higher domain \#CSP
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• A dichotomy for real weighted Holant problems
• A complete dichotomy rises from the capture of vanishing signatures
• The complexity of counting homomorphisms to cactus graphs modulo 2
• The complexity of Boolean Holant problems with nonnegative weights
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• scientific article; zbMATH DE number 7204481 (Why is no real title available?)
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Perfect matchings, rank of connection tensors and graph homomorphisms
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• Bipartite 3-regular counting problems with mixed signs
• Bipartite 3-regular counting problems with mixed signs
• The computational complexity of Holant problems on 3-regular graphs
• Restricted Holant dichotomy on domains 3 and 4
• Restricted Holant dichotomy on domain sizes 3 and 4
• A combinatorial view of Holant problems on higher domains
• Parameterised holant problems

This page was built for publication: The complexity of symmetric Boolean parity Holant problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891075)