{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:10:21Z","timestamp":1763467821358,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_55","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"631-642","source":"Crossref","is-referenced-by-count":5,"title":["Holographic Algorithms: The Power of Dimensionality Resolved"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/11786986_61","volume-title":"Automata, Languages and Programming","author":"J.-Y. Cai","year":"2006","unstructured":"Cai, J-Y., Choudhary, V.: Some Results on Matchgates and Holographic Algorithms. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051(Part I), pp. 703\u2013714. Springer, Heidelberg (2006) Also available at Electronic Colloquium on Computational Complexity TR06-048, 2006"},{"key":"55_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/11750321_24","volume-title":"Theory and Applications of Models of Computation","author":"J.-Y. Cai","year":"2006","unstructured":"Cai, J-Y., Choudhary, V.: Valiant\u2019s Holant Theorem and Matchgate Tensors (Extended Abstract). In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 248\u2013261. Springer, Heidelberg (2006) Also available at Electronic Colloquium on Computational Complexity Report TR05-118"},{"key":"55_CR3","doi-asserted-by":"crossref","unstructured":"Cai, J-Y., Choudhary, V., Lu, P.: On the Theory of Matchgate Computations. In: CCC 2007 (to appear)","DOI":"10.1109\/CCC.2007.22"},{"key":"55_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-540-70918-3_37","volume-title":"STACS 2007","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J-Y., Lu, P.: On Symmetric Signatures in Holographic Algorithms. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 429\u2013440. Springer, Heidelberg (2007)"},{"key":"55_CR5","doi-asserted-by":"crossref","unstructured":"Cai, J-Y., Lu, P.: Holographic Algorithms: From Art to Science. To appear in STOC 2007. Also available at Electronic Colloquium on Computational Complexity Report TR06-145","DOI":"10.1145\/1250790.1250850"},{"key":"55_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J-Y., Lu, P.: Bases Collapse in Holographic Algorithms. In: CCC 2007. Also available at Electronic Colloquium on Computational Complexity Report TR07-003 (to appear)","DOI":"10.1109\/CCC.2007.6"},{"key":"55_CR7","unstructured":"Cai, J-Y., Lu, P.: Holographic Algorithms: The Power of Dimensionality Resolved. Available at Electronic Colloquium on Computational Complexity Report TR07-020"},{"key":"55_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-10514-2","volume-title":"Tensor Geometry. Graduate Texts in Mathematics","author":"C.T.J. Dodson","year":"1991","unstructured":"Dodson, C.T.J., Poston, T.: Tensor Geometry. Graduate Texts in Mathematics, 2nd edn., vol.\u00a0130. Springer, Heidelberg (1991)","edition":"2"},{"issue":"2","key":"55_CR9","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"2000","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput.\u00a011(2), 329\u2013343 (2000)","journal-title":"SIAM J. Comput."},{"key":"55_CR10","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01010403","volume":"48","author":"M. Jerrum","year":"1987","unstructured":"Jerrum, M.: Two-dimensional monomer-dimer systems are computationally intractable. J. Stat. Phys.\u00a048, 121\u2013134 (1987) erratum. 59, 1087-1088 (1990)","journal-title":"J. Stat. Phys."},{"key":"55_CR11","doi-asserted-by":"publisher","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\u00a027, 1209\u20131225 (1961)","journal-title":"Physica"},{"key":"55_CR12","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. 43\u2013110. Academic Press, London (1967)"},{"key":"55_CR13","unstructured":"Knill, E.: Fermionic Linear Optics and Matchgates. At http:\/\/arxiv.org\/abs\/quant-ph\/0108033"},{"key":"55_CR14","volume-title":"Matrices and Matroids for Systems Analysis","author":"K. Murota","year":"2000","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Heidelberg (2000)"},{"key":"55_CR15","doi-asserted-by":"publisher","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 \u2013 an exact result. Philosophical Magazine\u00a06, 1061\u20131063 (1961)","journal-title":"Philosophical Magazine"},{"issue":"4","key":"55_CR16","doi-asserted-by":"publisher","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 Journal of Computing\u00a031(4), 1229\u20131254 (2002)","journal-title":"SIAM Journal of Computing"},{"issue":"1","key":"55_CR17","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0281(1), 457\u2013471 (2002)","journal-title":"Theoretical Computer Science"},{"key":"55_CR18","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Holographic Algorithms (Extended Abstract). In: Proc. 45th IEEE Symposium on Foundations of Computer Science, pp. 306\u2013315 (2004) A more detailed version appeared in Electronic Colloquium on Computational Complexity Report TR05-099","DOI":"10.1109\/FOCS.2004.34"},{"key":"55_CR19","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Holographic circuits. In: Proc. 32nd International Colloquium on Automata, Languages and Programming, pp. 1\u201315 (2005)","DOI":"10.1007\/11523468_1"},{"key":"55_CR20","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness for parity problems. In: Proc. 11th International Computing and Combinatorics Conference, pp. 1\u20138 (2005)","DOI":"10.1007\/11533719_1"},{"key":"55_CR21","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental Algorithms. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:15:35Z","timestamp":1737393335000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}