The complexity of symmetric Boolean parity Holant problems
DOI10.1137/100815530zbMATH Open1286.68232OpenAlexW2000217912MaRDI QIDQ5891075FDOQ5891075
Leslie G. Valiant, Heng Guo, Pinyan Lu
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
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)
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)
Cited In (16)
- A dichotomy for real weighted Holant problems
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Title not available (Why is that?)
- On blockwise symmetric matchgate signatures and higher domain \#CSP
- Restricted Holant dichotomy on domains 3 and 4
- Perfect matchings, rank of connection tensors and graph homomorphisms
- The computational complexity of Holant problems on 3-regular graphs
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- 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
- Restricted Holant dichotomy on domain sizes 3 and 4
- FKT is not universal -- a planar holant dichotomy for symmetric constraints
- The complexity of planar Boolean \#CSP with complex weights
- The Complexity of Boolean Holant Problems with Nonnegative Weights
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)
