Matchgates Revisited

by Jin-Yi Cai and Aaron Gorenstein

Theory of Computing, Volume 10(7), pp. 167-197, 2014

Bibliography with links to cited articles

[1]   Jin-Yi Cai and Vinay Choudhary: Some results on matchgates and holographic algorithms. Int. J. Software and Informatics, 1(1):3–36, 2007. See at IJSI. Preliminary version in ICALP’06. See also at ECCC.

[2]    Jin-Yi Cai, Vinay Choudhary, and Pinyan Lu: On the theory of matchgate computations. Theory Comput. Syst., 45(1):108–132, 2009. Preliminary version in CCC’07. See also at ECCC. [doi:10.1007/s00224-007-9092-8]

[3]   Jin-Yi Cai, Heng Guo, and Tyson Williams: A complete dichotomy rises from the capture of vanishing signatures: extended abstract. In Proc. 45th STOC, pp. 635–644. ACM Press, 2013. See also at arXiv. [doi:10.1145/2488608.2488687]

[4]   Jin-Yi Cai, Michael R. Kowalczyk, and Tyson Williams: Gadgets and anti-gadgets leading to a complexity dichotomy. In Proc. 3rd Symp. Innovations in Theoretical Computer Science (ITCS’12), pp. 452–467. ACM Press, 2012. See also at arXiv. [doi:10.1145/2090236.2090272]

[5]   Jin-Yi Cai and Pinyan Lu: Holographic algorithms: The power of dimensionality resolved. Theoret. Comput. Sci., 410(18):1618–1628, 2009. Preliminary version in ICALP’07. See also at ECCC. [doi:10.1016/j.tcs.2008.12.047]

[6]   Jin-Yi Cai and Pinyan Lu: On blockwise symmetric signatures for matchgates. Theoret. Comput. Sci., 411(4-5):739–750, 2010. Preliminary version in FCT’07. See also at ECCC. [doi:10.1016/j.tcs.2009.10.012]

[7]   Jin-Yi Cai and Pinyan Lu: Holographic algorithms: From art to science. J. Comput. System Sci., 77(1):41–61, 2011. Preliminary version in STOC’07. See also at ECCC. [doi:10.1016/j.jcss.2010.06.005]

[8]   Jin-Yi Cai and Pinyan Lu: Signature theory in holographic algorithms. Algorithmica, 61(4):779–816, 2011. Preliminary version in ISAAC’08. [doi:10.1007/s00453-009-9383-3]

[9]   Jin-Yi Cai, Pinyan Lu, and Mingji Xia: Holographic algorithms with matchgates capture precisely tractable planar #CSP. In Proc. 51st FOCS, pp. 427–436. IEEE Comp. Soc. Press, 2010. See also at arXiv. [doi:10.1109/FOCS.2010.48]

[10]   Andreas W.M. Dress and Walter Wenzel: A simple proof of an identity concerning Pfaffians of skew symmetric matrices. Advances in Mathematics, 112(1):120–134, 1995. [doi:10.1006/aima.1995.1029]

[11]   Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia: The complexity of weighted Boolean #CSP modulo k. In Proc. 28th Symp. Theoretical Aspects of Comp. Sci. (STACS’11), pp. 249–260. Schloss Dagstuhl, 2011. [doi:10.4230/LIPIcs.STACS.2011.249]

[12]   Heng Guo, Pinyan Lu, and Leslie G. Valiant: The complexity of symmetric Boolean parity Holant problems. SIAM J. Comput., 42(1):324–356, 2013. Preliminary version in ICALP’11. [doi:10.1137/100815530]

[13]   Heng Guo and Tyson Williams: The complexity of planar Boolean #CSP with complex weights. In Proc. 40th Internat. Colloq. on Automata, Languages and Programming (ICALP’13), pp. 516–527. Springer, 2013. See also at arXiv. [doi:10.1007/978-3-642-39206-1_44]

[14]   Pieter Willem Kasteleyn: Graph theory and crystal physics. In Frank Harary, editor, Graph Theory and Theoretical Physics, pp. 43–110. Academic Press, 1967.

[15]   Michael Kowalczyk: Dichotomy Theorems for Holant Problems. Ph. D. thesis, University of Wisconsin–Madison, 2010. Available at author’s home page. [ACM:2049085]

[16]   Joseph M. Landsberg, Jason Morton, and Serguei Norine: Holographic algorithms without matchgates. Linear Algebra and its Applications, 438(2):782–795, 2013. See also at arXiv. [doi:10.1016/j.laa.2012.01.010]

[17]   Angsheng Li and Mingji Xia: A theory for Valiant’s matchcircuits (extended abstract). In Proc. 25th Symp. Theoretical Aspects of Comp. Sci. (STACS’08), pp. 491–502. Schloss Dagstuhl, 2008. See also at arXiv. [doi:10.4230/LIPIcs.STACS.2008.1368]

[18]   Jason Morton: Pfaffian circuits. Technical report, 2010. [arXiv:1101.0129]

[19]   Kazuo Murota: Matrices and Matroids for Systems Analysis. Volume 20 of Algorithms and Combinatorics. Springer, 2000. [doi:10.1007/978-3-642-03994-2]

[20]   Yasuhiro Ohta: Bilinear Theory of Soliton. Ph. D. thesis, University of Tokyo, 1992.

[21]   Harold N. V. Temperley and Michael E. Fisher: Dimer problem in statistical mechanics–an exact result. Philosophical Magazine, 6(68):1061–1063, 1961. [doi:10.1080/14786436108243366]

[22]   Robin Thomas: A survey of Pfaffian orientations of graphs. In Marta Sanz-Solé, Javier Soria, Juan Luis Varona, and Joan Verdera, editors, Proceedings of the International Congress of Mathematicians, volume 3, pp. 963–984, Madrid, 2006. European Mathematical Society Publishing House. [doi:10.4171/022-3/47]

[23]   Leslie G. Valiant: Expressiveness of matchgates. Theoret. Comput. Sci., 289(1):457–471, 2002. [doi:10.1016/S0304-3975(01)00325-5]

[24]   Leslie G. Valiant: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput., 31(4):1229–1254, 2002. Preliminary version in STOC’01. [doi:10.1137/S0097539700377025]

[25]   Leslie G. Valiant: Accidental algorithms. In Proc. 47th FOCS, pp. 509–517. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.7]

[26]   Leslie G. Valiant: Holographic algorithms. SIAM J. Comput., 37(5):1565–1594, 2008. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/070682575]