Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-048 | 9th April 2006 00:00

Some Results on Matchgates and Holographic Algorithms

RSS-Feed




TR06-048
Authors: Jin-Yi Cai, Vinay Choudhary
Publication: 18th April 2006 12:00
Downloads: 3423
Keywords: 


Abstract:

We establish a 1-1 correspondence between Valiant's
character theory of matchgate/matchcircuit
and his signature theory of planar-matchgate/matchgrid,
thus unifying the two theories in expressibility.
Previously we had established a complete characterization
of general matchgates, in terms of a set of
useful Grassmann-Pl{\"u}cker 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.



ISSN 1433-8092 | Imprint