Signature theory in holographic algorithms (Q652529)

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 equations called matchgate identities (MGI), implicitly used in the paper in the form of explicit Pfaffian representations. Using algebraic proof techniques characterization theorems concerning 1-realizability and 1-admissibility are also given. Finally, some new holographic algorithms using this general theory of unsymmetric signatures are presented for three problems solvable in polynomial time, on the number of 2-colorings of curves between \(n\) points on a plane, satisfying some requirements.