A collapse theorem for holographic algorithms with matchgates on domain size at most 4

DOI10.1016/j.ic.2014.10.002zbMath1309.68085arXiv1305.1409MaRDI QIDQ476175

Jin-Yi Cai, Zhiguo Fu

Publication date: 28 November 2014

Published in: Information and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

Related Items

Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Holographic algorithms on domains of general size, On blockwise symmetric matchgate signatures and higher domain \#CSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spin systems on \(k\)-regular graphs with complex edge functions
• The complexity of planar Boolean \#CSP with complex weights
• Holographic algorithms on bases of rank 2
• Gadgets and anti-gadgets leading to a complexity dichotomy
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• The statistics of dimers on a lattice
• The Complexity of the Counting Constraint Satisfaction Problem
• Some Observations on Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• Quantum computers that can be simulated classically in polynomial time
• Dimer problem in statistical mechanics-an exact result
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Complexity of counting CSP with complex weights
• Holographic Algorithms: The Power of Dimensionality Resolved
• A complete dichotomy rises from the capture of vanishing signatures
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• The completeness of the first-order functional calculus
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem
• The Complexity of Symmetric Boolean Parity Holant Problems