Signature theory in holographic algorithms

DOI10.1007/s00453-009-9383-3zbMath1238.68184OpenAlexW2149409888MaRDI QIDQ652529

Pinyan Lu, Jin-Yi Cai

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

manifoldgeneratorCatalan numbersignatureplanar graph2-coloringperfect matchingcomplexity theorytensor spacecounting problemsholographic algorithms\(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)

Related Items

Erratum to: ``Signature theory in holographic algorithms ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Holographic algorithms beyond matchgates ⋮ Holographic algorithms on bases of rank 2 ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• On theory and applications of BIB designs with repeated blocks
• Expressiveness of matchgates.
• A combinatorical proof of Kneser's conjecture
• The statistics of dimers on a lattice
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Signature Theory in Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• On the Structure oft-Designs
• Incidence Matrices of Subsets—A Rank Formula
• Tensor Geometry
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms: The Power of Dimensionality Resolved
• Theory and Applications of Models of Computation