Signature theory in holographic algorithms

DOI10.1007/S00453-009-9383-3zbMATH Open1238.68184OpenAlexW2149409888MaRDI QIDQ652529FDOQ652529

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

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

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)

Cites Work

• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Tensor Geometry
• Dimer problem in statistical mechanics-an exact result
• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Some Results on Matchgates and Holographic Algorithms
• A combinatorical proof of Kneser's conjecture
• On the Structure oft-Designs
• On theory and applications of BIB designs with repeated blocks
• 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
• Title not available (Why is that?)
• Incidence Matrices of Subsets—A Rank Formula

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)