{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:40Z","timestamp":1725511780610},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_37","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"429-440","source":"Crossref","is-referenced-by-count":10,"title":["On Symmetric Signatures in Holographic Algorithms"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","first-page":"248","volume-title":"ACM SODA","author":"R. Bubley","year":"1997","unstructured":"Bubley, R., Dyer, M.: Graph orientations with no sink and an approximation for a hard case of #SAT. In: ACM SODA, pp. 248\u2013257. ACM Press, New York (1997)"},{"key":"37_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. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 248\u2013261. Springer, Heidelberg (Also available as ECCC TR05-118) (2006)"},{"key":"37_CR3","unstructured":"Cai, J.-Y., Choudhary, V.: On the Theory of Matchgate Computations. Submitted. Also available as ECCC TR06-018"},{"key":"37_CR4","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., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 703\u2013714. Springer, Heidelberg (2006)"},{"key":"37_CR5","unstructured":"Cai, J.-Y., Lu, P.: On Symmetric Signatures in Holographic Algorithms. Available at Electronic Colloquium on Computational Complexity Report TR06-135"},{"issue":"4","key":"37_CR6","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H.B. Hunt","year":"1998","unstructured":"Hunt, H.B., et al.: The complexity of planar counting problems. SIAM J. Comput.\u00a027(4), 1142\u20131167 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"37_CR7","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/0219003","volume":"19","author":"H.B. Hunt III.","year":"1990","unstructured":"Hunt III., H.B., Stearns, R.E.: The complexity of very simple Boolean formulas with applications. SIAM J. Comput.\u00a019(1), 44\u201370 (1990)","journal-title":"SIAM J. Comput."},{"key":"37_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":"37_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":"37_CR10","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. on Computing\u00a011, 329\u2013343 (1982)","journal-title":"SIAM J. on Computing"},{"key":"37_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":"37_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":"4","key":"37_CR13","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"},{"issue":"1","key":"37_CR14","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 (See also 299, 795) (2002)","journal-title":"Theoretical Computer Science"},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/FOCS.2004.34","volume-title":"Proc. 45th IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2004","unstructured":"Valiant, L.G.: Holographic Algorithms (Extended Abstract). In: Proc. 45th IEEE Symposium on Foundations of Computer Science, pp. 306\u2013315. IEEE Computer Society Press, Los Alamitos (A more detailed version appeared in Electronic Colloquium on Computational Complexity Report TR05-099) (2004)"},{"key":"37_CR16","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Automata, Languages and Programming","author":"L.G. Valiant","year":"2005","unstructured":"Valiant, L.G.: Holographic circuits. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1\u201315. Springer, Heidelberg (2005)"},{"key":"37_CR17","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"},{"key":"37_CR18","first-page":"509","volume-title":"Proc. 47th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2006","unstructured":"Valiant, L.G.: Accidental Algorithms. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517. IEEE Computer Society Press, Los Alamitos (2006)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:32:09Z","timestamp":1620016329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_37","relation":{},"subject":[]}}