A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs

DOI10.1016/j.tcs.2012.03.036zbMath1253.68184OpenAlexW1550829276MaRDI QIDQ443724

Tomoyuki Yamakami

Publication date: 13 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.036

zbMATH Keywords

signatureconstraint satisfaction problemapproximate countingbounded degreedichotomy theorem\(\#\)CSPholant problemT-constructibility

Mathematics Subject Classification ID

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

Related Items (2)

A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Holographic algorithms: from art to science
• An approximation trichotomy for Boolean \#CSP
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
• Complexity of generalized satisfiability counting problems
• The Complexity of Approximating Bounded-Degree Boolean #CSP
• On Counting Independent Sets in Sparse Graphs
• Holographic Algorithms
• Signature Theory in Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• On the Structure of Polynomial Time Reducibility
• Holant problems and counting CSP
• The complexity of satisfiability problems
• Mathematical Foundations of Computer Science 2003
• Fanout limitations on constraint systems

This page was built for publication: A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs