From Holant to \#CSP and back: dichotomy for Holant^c problems

DOI10.1007/978-3-642-17517-6_24MaRDI QIDQ3060738zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Sangxia Huang, Pinyan Lu

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17517-6_24

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Holant problems and counting CSP
• Computational complexity of Holant problems
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Dichotomy for Holant* problems of Boolean domain

Cited in

(18)

• Zero-free regions of partition functions with applications to algorithms and graph limits
• Holographic reduction, interpolation and hardness
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Holographic reduction for some counting problems
• A dichotomy for real weighted Holant problems
• Computational complexity of Holant problems
• Holographic reduction: a domain changed application and its partial converse theorems
• The complexity of complex weighted Boolean \#CSP
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• A New Holant Dichotomy Inspired by Quantum Computation
• Holant problems and counting CSP
• Zeros of Holant problems: locations and algorithms
• Classification of a Class of Counting Problems Using Holographic Reductions
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
• Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)

This page was built for publication: From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems

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