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

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)

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

(16)

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

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)