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: 5261
Download times: 3109
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



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences

京公网安备 11040202500065号