A collapse theorem for holographic algorithms with matchgates on domain size at most 4
From MaRDI portal
Publication:476175
DOI10.1016/j.ic.2014.10.002zbMath1309.68085arXiv1305.1409OpenAlexW2123157085MaRDI QIDQ476175
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
Related Items (3)
On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Holographic algorithms on domains of general size
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
This page was built for publication: A collapse theorem for holographic algorithms with matchgates on domain size at most 4
