On symmetric signatures in holographic algorithms

DOI10.1007/S00224-009-9229-ZzbMATH Open1204.68256OpenAlexW2045616322MaRDI QIDQ968267FDOQ968267

Authors: Jin-Yi Cai, Pinyan Lu 

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

Recommendations

• On Symmetric Signatures in Holographic Algorithms
• Signature theory in holographic algorithms
• Basis collapse for holographic algorithms over all domain sizes
• Holographic algorithms: from art to science
• Holographic algorithms: from art to science

zbMATH Keywords

realizabilityholographic algorithms0-1 signaturesmatchgates and signaturessymmetric signatures

Mathematics Subject Classification ID

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

Cites Work

• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Dimer problem in statistical mechanics-an exact result
• Title not available (Why is that?)
• Planar Formulae and Their Uses
• Matrices and matroids for systems analysis
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Some Results on Matchgates and Holographic Algorithms
• Title not available (Why is that?)
• The Complexity of Planar Counting Problems
• Signature Theory in Holographic Algorithms
• Holographic algorithms: from art to science
• Holographic Algorithms: The Power of Dimensionality Resolved
• Expressiveness of matchgates.
• Theory and Applications of Models of Computation
• On Symmetric Signatures in Holographic Algorithms
• Title not available (Why is that?)
• The Complexity of Very Simple Boolean Formulas with Applications
• On Block-Wise Symmetric Signatures for Matchgates

Cited In (7)

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

This page was built for publication: On symmetric signatures in holographic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968267)