{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T06:48:33Z","timestamp":1769755713387,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,7,21]],"date-time":"2009-07-21T00:00:00Z","timestamp":1248134400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00224-009-9229-z","type":"journal-article","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T18:20:41Z","timestamp":1248114041000},"page":"398-415","source":"Crossref","is-referenced-by-count":14,"title":["On Symmetric Signatures in Holographic Algorithms"],"prefix":"10.1007","volume":"46","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,7,21]]},"reference":[{"key":"9229_CR1","unstructured":"Bubley, R., Dyer, M.: Graph orientations with no sink and an approximation for a hard case of #SAT. In: ACM SODA, pp.\u00a0248\u2013257 (1997)"},{"key":"9229_CR2","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Choudhary, V.: Valiant\u2019s Holant theorem and matchgate tensors. In: Proceedings of TAMC 2006. Lecture Notes in Computer Science, vol.\u00a03959, pp.\u00a0248\u2013261. Theor. Comput. Sci. 384(1), 22\u201332 (2007). Also available as ECCC TR05-118","DOI":"10.1016\/j.tcs.2007.05.015"},{"key":"9229_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1007\/978-3-540-72504-6","volume-title":"Proceedings of ICALP 2006, Part I","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Choudhary, V.: Some results on matchgates and holographic algorithms. In: Proceedings of ICALP 2006, Part I. Lecture Notes in Computer Science, vol.\u00a04051, pp.\u00a0703\u2013714. Springer, Berlin (2007). Int. J. Softw. Inf. 1(1), 3\u201336"},{"key":"9229_CR4","first-page":"305","volume-title":"Proceedings of CCC\u201907: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Choudhary, V., Lu, P.: On the theory of matchgate computations. In: Proceedings of CCC\u201907: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, pp.\u00a0305\u2013318. IEEE Computer Society, Washington (2007)"},{"key":"9229_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/978-3-540-70918-3_37","volume-title":"Proceedings of STACS","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Lu, P.: On symmetric signatures in holographic algorithms. In: Thomas, W., Weil, P. (eds.) Proceedings of STACS. Lecture Notes in Computer Science, vol.\u00a04393, pp.\u00a0429\u2013440. Springer, Berlin (2007)"},{"key":"9229_CR6","first-page":"401","volume-title":"Proceedings of STOC\u201907: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: from art to science. In: Proceedings of STOC\u201907: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp.\u00a0401\u2013410. ACM, New York (2007)"},{"key":"9229_CR7","first-page":"292","volume-title":"Proceedings of CCC \u201907: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Lu, P.: Bases collapse in holographic algorithms. In: Proceedings of CCC \u201907: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, pp.\u00a0292\u2013304. IEEE Computer Society, Washington (2007). Comput. Complexity 17(2), 254\u2013281 (2008)"},{"key":"9229_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1007\/978-3-540-73420-8_55","volume-title":"Proceedings of ICALP","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: the power of dimensionality resolved. In: Arge, L., Cachin, C., Jurdzinski, T. et al. (eds.) Proceedings of ICALP. Lecture Notes in Computer Science, vol.\u00a04596, pp.\u00a0631\u2013642. Springer, Berlin (2007)"},{"key":"9229_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/978-3-540-74240-1_17","volume-title":"Proceedings of FCT","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Lu, P.: On block-wise symmetric signatures for matchgates. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) Proceedings of FCT. Lecture Notes in Computer Science, vol.\u00a04639, pp.\u00a0187\u2013198. Springer, Berlin (2007)"},{"key":"9229_CR10","first-page":"54","volume-title":"Proceedings of SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J.-Y. Cai","year":"2008","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms with unsymmetric signatures. In: Proceedings of SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a054\u201363. SIAM, Philadelphia (2008)"},{"key":"9229_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-92182-0_51","volume-title":"Proceedings of ISAAC","author":"J.-Y. Cai","year":"2008","unstructured":"Cai, J.-Y., Lu, P.: Signature theory in holographic algorithms. In: Hong, S.H., Nagamochi, H., Fukunaga, T. (eds.) Proceedings of ISAAC. Lecture Notes in Computer Science, vol.\u00a05369, pp.\u00a0568\u2013579. Springer, Berlin (2008)"},{"issue":"4","key":"9229_CR12","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H.B. Hunt","year":"1998","unstructured":"Hunt, H.B., Marathe, M.V., Radhakrishnan, V., Stearns, R.E.: The complexity of planar counting problems. SIAM J. Comput. 27(4), 1142\u20131167 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9229_CR13","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1137\/0219003","volume":"19","author":"H.B. Hunt III","year":"1990","unstructured":"Hunt, H.B. III, Stearns, R.E.: The complexity of very simple Boolean formulas with applications. SIAM J. Comput. 19(1), 44\u201370 (1990)","journal-title":"SIAM J. Comput."},{"key":"9229_CR14","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"P.W. Kasteleyn","year":"1961","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice. Physica 27, 1209\u20131225 (1961)","journal-title":"Physica"},{"key":"9229_CR15","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"P.W. Kasteleyn","year":"1967","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp.\u00a043\u2013110. Academic Press, London (1967)"},{"key":"9229_CR16","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"9229_CR17","volume-title":"Matrices and Matroids for Systems Analysis","author":"K. Murota","year":"2000","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Berlin (2000)"},{"key":"9229_CR18","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"H.N.V. Temperley","year":"1961","unstructured":"Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics\u2014an exact result. Philos. Mag. 6, 1061\u20131063 (1961)","journal-title":"Philos. Mag."},{"issue":"4","key":"9229_CR19","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"L.G. Valiant","year":"2002","unstructured":"Valiant, L.G.: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput. 31(4), 1229\u20131254 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9229_CR20","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/S0304-3975(01)00325-5","volume":"281","author":"L.G. Valiant","year":"2002","unstructured":"Valiant, L.G.: Expressiveness of matchgates. Theor. Comput. Sci. 281(1), 457\u2013471 (2002). See also Theor. Comput. Sci. 299, 795 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9229_CR21","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Holographic algorithms (extended abstract). In: Proc. 45th IEEE Symposium on Foundations of Computer Science, pp.\u00a0306\u2013315 (2004). A more detailed version appeared in Electronic Colloquium on Computational Complexity Report TR05-099","DOI":"10.1109\/FOCS.2004.34"},{"key":"9229_CR22","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental algorithms. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9229-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9229-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9229-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T05:32:37Z","timestamp":1739251957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9229-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,21]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9229"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9229-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,21]]}}}