scientific article; zbMATH DE number 7204481

DOI10.4230/LIPICS.ICALP.2017.29MaRDI QIDQ5111359zbMATH OpenFDO

Authors Jiabao Lin, Hanpin Wang

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1611.00975

zbMATH Keywords

counting complexitydichotomy\#CSPHolant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of Boolean Holant problems with nonnegative weights
• On the Complexity of Holant Problems
• The complexity of symmetric Boolean parity Holant problems
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• The complexity of complex weighted Boolean \#CSP
• Computational complexity of Holant problems
• The Complexity of Weighted Boolean #CSP
• Zero-freeness and approximation of real Boolean Holant problems

Cited in

(9)

• Zeros and approximations of holant polynomials on the complex plane
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• The complexity of Boolean Holant problems with nonnegative weights
• Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
• A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• Clifford gates in the Holant framework
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Dichotomy result on 3-regular bipartite non-negative functions

This page was built for publication:

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