| Some Results on Matchgates and Holographic Algorithms |
| Received:May 10, 2007 Revised:October 18, 2007 Download PDF |
| Jin-Yi Cai,Vinay Choudhary. Some Results on Matchgates and Holographic Algorithms. International Journal of Software and Informatics, 2007,1(1):3~36 |
| Hits: 5604 |
| Download times: 3553 |
| Jin-Yi Cai Vinay Choudhary |
|
| Fund:Supported by NSF CCR-0208013, CCR-0511679, and in part by the National Basic Research Program of China Grant 2007CB807900, 2007CB807901. An extended abstract of this paper appearedin ICALP 06 [1].Supported by NSF CCR-0208013. |
|
| Abstract:We establish a 1-1 correspondence between Valiant's character theory of match-gate/matchcircuit [13] and his signature theory of planarmatchgate/matchgrid [15], thus unifying the two theories in expressibility. In [3], we established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Plucker identities. The 1-1 correspondence established in this paper gives 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. |
| keywords:computational complexity holographic algorithms |
| View Full Text View/Add Comment Download reader |
