Some Results on Matchgates and Holographic Algorithms.
Jin‐Yi Cai, Vinay Choudhary
We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.
Electronic colloquium on computational complexity•Jan 1, 2006•1 citation