On blockwise symmetric matchgate signatures and higher domain \#CSP

DOI10.1016/j.ic.2018.09.012zbMath1408.68074arXiv1707.00373OpenAlexW2963920790MaRDI QIDQ1633804

Fengqin Yang, Minghao Yin, Zhiguo Fu

Publication date: 21 December 2018

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

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

zbMATH Keywords

matchgate\#CSPblockwise symmetryholographic transformation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Holographic algorithms on domains of general size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• The complexity of computing the permanent
• On blockwise symmetric signatures for matchgates
• Holographic algorithms: the power of dimensionality resolved
• Expressiveness of matchgates.
• Holographic algorithms without matchgates
• The complexity of planar Boolean \#CSP with complex weights
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• The statistics of dimers on a lattice
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• Some Observations on Holographic Algorithms
• The Complexity of Enumeration and Reliability Problems
• Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
• Holant problems and counting CSP
• Dimer problem in statistical mechanics-an exact result
• Basis collapse for holographic algorithms over all domain sizes
• Base collapse of holographic algorithms
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• The Complexity of Symmetric Boolean Parity Holant Problems