ECCC-Report TR06-048https://eccc.weizmann.ac.il/report/2006/048Comments and Revisions published for TR06-048en-usTue, 18 Apr 2006 12:00:11 +0300
Paper TR06-048
| Some Results on Matchgates and Holographic Algorithms |
Jin-Yi Cai,
Vinay Choudhary
https://eccc.weizmann.ac.il/report/2006/048We 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.
Tue, 18 Apr 2006 12:00:11 +0300https://eccc.weizmann.ac.il/report/2006/048