Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain

DOI10.1137/17M1131672OpenAlexW2985956690MaRDI QIDQ5073518

Jin-Yi Cai, Zhiguo Fu

Publication date: 3 May 2022

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

Full work available at URL: https://doi.org/10.1137/17m1131672

zbMATH Keywords

holographic algorithmsmatchgates\#CSP

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 (4)

Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ On the dimer problem of the vertex-edge graph of a cubic graph ⋮ Complexity classification of the eight-vertex model ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• The complexity of complex weighted Boolean \#CSP
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• Signature theory in holographic algorithms
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Holographic algorithms: the power of dimensionality resolved
• Expressiveness of matchgates.
• Complexity of generalized satisfiability counting problems
• Holographic algorithms by Fibonacci gates
• Holographic algorithms without matchgates
• The complexity of planar Boolean \#CSP with complex weights
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• The statistics of dimers on a lattice
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Computational Complexity of Holant Problems
• Polynomial-Time Approximation Algorithms for the Ising Model
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• Complexity Dichotomies for Counting Problems
• Beitrag zur Theorie des Ferromagnetismus
• Holant problems and counting CSP
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• Dichotomy for Holant Problems with a Function on Domain Size 3
• The Spontaneous Magnetization of a Two-Dimensional Ising Model
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• The Complexity of Symmetric Boolean Parity Holant Problems

This page was built for publication: Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain