{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:51:05Z","timestamp":1787496665949,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_61","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"703-714","source":"Crossref","is-referenced-by-count":13,"title":["Some Results on Matchgates and Holographic Algorithms"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vinay","family":"Choudhary","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"61_CR1","unstructured":"Aitken, A.C.: Determinants and Matrices, Oliver and Boyd, London (1951)"},{"key":"61_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11750321","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. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, Springer, Heidelberg (2006)"},{"key":"61_CR3","unstructured":"Cai, J.-Y., Choudhary, V.: On the Theory of Matchgate Computations. Submitted. Also available at ECCC TR06-018"},{"key":"61_CR4","unstructured":"Cai, J.-Y., Choudhary, V.: Some Results on Matchgates and Holographic Algorithms. ECCC TR06-048"},{"key":"61_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM Journal on Computing\u00a04, 221\u2013225 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"61_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/3-540-44693-1_32","volume-title":"STACS 2001","author":"K. Jansen","year":"2001","unstructured":"Jansen, K., Karpinski, M., Lingas, A., Seidel, E.: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 365\u2013375. Springer, Heidelberg (2001)"},{"key":"#cr-split#-61_CR7.1","doi-asserted-by":"crossref","unstructured":"Jerrum, M.R.: Two-dimensional Monomer-Dimer Systems are Computationally Intractable. Journal of Statistical Physics 48 (1\/2), 121-134 (1987)","DOI":"10.1007\/BF01010403"},{"key":"#cr-split#-61_CR7.2","doi-asserted-by":"crossref","unstructured":"also 59 (3\/4), 1087-1088 (1990)","DOI":"10.1007\/BF01025864"},{"key":"61_CR8","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":"61_CR9","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":"61_CR10","first-page":"309","volume-title":"The Theory of Error-Correcting Codes","author":"F. MacWilliams","year":"1977","unstructured":"MacWilliams, F., Sloane, N.: The Theory of Error-Correcting Codes, p. 309. NorthHolland, Amsterdam (1977)"},{"key":"61_CR11","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":"61_CR12","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":"1","key":"61_CR13","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"8","author":"S.P. Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The Complexity of Counting in Sparse, Regular and Planar Graphs. SIAM Journal on Computing\u00a08(1), 398\u2013427 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"61_CR14","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 on Computing\u00a031(4), 1229\u20131254 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"61_CR15","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Expressiveness of Matchgates. Theoretical Computer Science 281(1), 457-471 (2002); See also 299, 795 (2003)","DOI":"10.1016\/S0304-3975(01)00325-5"},{"key":"61_CR16","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. A more detailed version appeared in Electronic Colloquium on Computational Complexity Report TR05-099 (2004)","DOI":"10.1109\/FOCS.2004.34"},{"key":"61_CR17","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":"61_CR18","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness for parity problems. In: Proc. 11th International Computing and Combinatorics Conference (2005)","DOI":"10.1007\/11533719_1"}],"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\/11786986_61","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T11:15:02Z","timestamp":1736421302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11786986_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}