A Complete Dichotomy Rises from the Capture of Vanishing Signatures

DOI10.1137/15M1049798zbMath1350.68133arXiv1204.6445MaRDI QIDQ2817798

Jin-Yi Cai, Heng Guo, Tyson Williams

Publication date: 2 September 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity; \#P; counting problems; dichotomy theorem; holographic algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Holographic algorithms beyond matchgates, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• A computational proof of complexity of some restricted counting problems
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• Spin systems on \(k\)-regular graphs with complex edge functions
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• Holographic algorithms beyond matchgates
• Complexity of generalized satisfiability counting problems
• Holographic reduction, interpolation and hardness
• Holographic algorithms by Fibonacci gates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the complexity of #CSP
• Computational Complexity of Holant Problems
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• Simulating Quantum Computation by Contracting Tensor Networks
• The Complexity of Weighted Boolean #CSP
• Tensor Geometry
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Codes on graphs: normal realizations
• Holant problems and counting CSP
• Classification of a Class of Counting Problems Using Holographic Reductions
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems
• Complexity of counting CSP with complex weights
• A complete dichotomy rises from the capture of vanishing signatures
• Operations with structures
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem