Signature theory in holographic algorithms
type: Item
instance of: scholarly article
title: Signature theory in holographic algorithms
zbMATH Open document ID: 1238.68184
author: Jin-Yi Cai
author: Pinyan Lu
published in: Algorithmica
publication date: 2011-12-14T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
review text: The theory of holographic algorithms was initiated by \textit{L. G. Valiant} [in: ``Holographic algorithms'', in: Proceedings of the 45th annual IEEE symposium on foundations of computer science, FOCS 2004. Los Alamitos, CA: IEEE. 306--315 (2004; \url{doi:10.1109/FOCS.2004.34})] and it allows to evaluate certain exponential sums in polynomial time. Ultimately the computation is reduced to the Fisher-Kasteleyn-Temperley method on planar perfect matchings via the Holant theorem. An algebraic framework which gave a satisfactory theory of symmetric signatures has been developed by the authors [in: Proceedings of the 39th annual ACM symposium on theory of computing, STOC'07. New York, NY: Association for Computing Machinery (ACM). 401--410 (2007; Zbl 1232.68055)]. They defined a basis manifold \({\mathcal M}\), and the signature theory was expressed in terms of \(d\)-admissibility and \(d\)-realizability, where \(d\) is the dimension of the algebraic variety of \({\mathcal M}\) corresponding to a desired signature. In this paper a Birkhoff-type theorem which gives a complete and explicit characterization of the class of 2-realizable signatures over characteristics 0 is proposed: If the family of matchgates with \(2k\) external nodes is denoted by \({\mathcal D}_{2k}\), then, up to a scale factor, every 2-realizable signature is obtainable as a planar tensor product from \((0,1,-1,0)\). For arity \(2k\), this is precisely the set of \(\frac{1}{k+1}{{2k}\choose {k}}\) signatures from \({\mathcal D}_{2k}\) which are 2-realizable, and it forms a basis of the solution space of the set of all 2-admissible signatures of arity \(2k\). It gives a complete structural understanding of the relationship between 2-realizability and 2-admissibility. An explicit combinatorial interpretation of 2-realizable signatures is given in terms of a planar tensor product of perfect matchings. In general, the realizability of signatures is controlled by an exponential sized set of algebraic equati…
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 68W01
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 94A62
zbMATH DE Number: 5988470
zbMATH Keywords: signature
zbMATH Keywords: holographic algorithms
zbMATH Keywords: \(d\)-realizability
zbMATH Keywords: \(d\)-admissibility
zbMATH Keywords: complexity theory
zbMATH Keywords: counting problems
zbMATH Keywords: manifold
zbMATH Keywords: tensor space
zbMATH Keywords: Catalan number
zbMATH Keywords: planar tensor product
zbMATH Keywords: matchgate identities
zbMATH Keywords: Pfaffian representations
zbMATH Keywords: planar graph
zbMATH Keywords: perfect matching
zbMATH Keywords: matchgrid
zbMATH Keywords: generator
zbMATH Keywords: 2-coloring
MaRDI profile type: Publication
OpenAlex ID: W2149409888
cites work: Some Results on Matchgates and Holographic Algorithms
cites work: Theory and Applications of Models of Computation
cites work: Q3549638
cites work: Holographic Algorithms: The Power of Dimensionality Resolved
cites work: Q3579392
cites work: Signature Theory in Holographic Algorithms
cites work: On theory and applications of BIB designs with repeated blocks
cites work: Tensor Geometry
cites work: On the Structure oft-Designs
cites work: Incidence Matrices of Subsets—A Rank Formula
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: A combinatorical proof of Kneser's conjecture
cites work: Dimer problem in statistical mechanics-an exact result
cites work: Quantum Circuits That Can Be Simulated Classically in Polynomial Time
cites work: Expressiveness of matchgates.
DOI: 10.1007/S00453-009-9383-3
description: scientific article; zbMATH DE number 5988470