Signature theory in holographic algorithms

DOI10.1007/S00453-009-9383-3MaRDI QIDQ652529zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Pinyan Lu

Publication date 14 December 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.483

zbMATH Keywords

Catalan numbermanifoldgeneratorcomplexity theoryperfect matchingplanar graphsignaturetensor spacecounting problemsholographic algorithms2-coloring\(d\)-admissibility\(d\)-realizabilitymatchgate identitiesmatchgridPfaffian representationsplanar tensor product

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Other designs, configurations (05B30) Authentication, digital signatures and secret sharing (94A62) General topics in the theory of algorithms (68W01)

Recommendations

• Signature Theory in Holographic Algorithms
• Holographic algorithms: from art to science
• Some Results on Matchgates and Holographic Algorithms
• Holographic algorithms: from art to science
• On Symmetric Signatures in Holographic Algorithms

Cites work

• scientific article; zbMATH DE number 5764803 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A combinatorical proof of Kneser's conjecture
• Dimer problem in statistical mechanics-an exact result
• Expressiveness of matchgates.
• Holographic Algorithms: The Power of Dimensionality Resolved
• Holographic algorithms: from art to science
• Incidence Matrices of Subsets—A Rank Formula
• Kneser's conjecture, chromatic number, and homotopy
• On the Structure oft-Designs
• On theory and applications of BIB designs with repeated blocks
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Signature Theory in Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• Tensor Geometry
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Theory and Applications of Models of Computation

Cited in

(9)

• Holographic algorithms on bases of rank 2
• Signature Theory in Holographic Algorithms
• On Symmetric Signatures in Holographic Algorithms
• Erratum to: ``Signature theory in holographic algorithms
• Holographic algorithms on domain size \(k > 2\)
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• On symmetric signatures in holographic algorithms
• Nearly-linear size holographic proofs
• Matchgates revisited

This page was built for publication: Signature theory in holographic algorithms

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