On symmetric signatures in holographic algorithms

DOI10.1007/s00224-009-9229-zzbMath1204.68256OpenAlexW2045616322MaRDI QIDQ968267

Pinyan Lu, Jin-Yi Cai

Publication date: 5 May 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9229-z

zbMATH Keywords

realizabilityholographic algorithms0-1 signaturesmatchgates and signaturessymmetric signatures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items

Holographic reduction, interpolation and hardness ⋮ Holographic algorithms: from art to science ⋮ Holographic algorithms on domains of general size ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expressiveness of matchgates.
• The statistics of dimers on a lattice
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The Complexity of Very Simple Boolean Formulas with Applications
• On Symmetric Signatures in Holographic Algorithms
• Signature Theory in Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• Planar Formulae and Their Uses
• The Complexity of Planar Counting Problems
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms: The Power of Dimensionality Resolved
• On Block-Wise Symmetric Signatures for Matchgates
• Theory and Applications of Models of Computation
• Matrices and matroids for systems analysis