{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:30:23Z","timestamp":1767141023557,"version":"build-2238731810"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,12,31]],"date-time":"2009-12-31T00:00:00Z","timestamp":1262217600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-009-9383-3","type":"journal-article","created":{"date-parts":[[2009,12,30]],"date-time":"2009-12-30T10:08:04Z","timestamp":1262167684000},"page":"779-816","source":"Crossref","is-referenced-by-count":5,"title":["Signature Theory in Holographic Algorithms"],"prefix":"10.1007","volume":"61","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,31]]},"reference":[{"key":"9383_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1007\/11786986_61","volume-title":"Proceedings of ICALP 2006, Part I","author":"J.-Y. Cai","year":"2006","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. 4051, pp. 703\u2013714. Springer, Berlin (2006). Also available at Electronic Colloquium on Computational Complexity TR06-048"},{"key":"9383_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/11750321_24","volume-title":"Proceedings of TAMC 2006","author":"J.-Y. Cai","year":"2006","unstructured":"Cai, J.-Y., Choudhary, V.: Valiant\u2019s Holant theorem and matchgate tensors (extended abstract). In: Proceedings of TAMC 2006. Lecture Notes in Computer Science, vol. 3959, pp. 248\u2013261. Springer, Berlin (2006). Also available at Electronic Colloquium on Computational Complexity Report TR05-118"},{"key":"9383_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1109\/CCC.2007.22","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, Washington, DC, USA, pp. 305\u2013318. IEEE Computer Society, Los Alamitos (2007)"},{"key":"9383_CR4","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1145\/1250790.1250850","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. 401\u2013410. ACM, New York (2007). Also available at Electronic Colloquium on Computational Complexity Report TR06-145"},{"key":"9383_CR5","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 \u201907","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: The power of dimensionality resolved. In: Arge, L., Cachin,\u00a0C., Jurdzinski, T., et al. (eds.) Proceedings of ICALP \u201907. Lecture Notes in Computer Science, vol. 4596, pp. 631\u2013642. Springer, Berlin (2007)"},{"key":"9383_CR6","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. 54\u201363. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"key":"9383_CR7","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. 5369, pp. 568\u2013579. Springer, Berlin (2008)"},{"key":"9383_CR8","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1214\/aos\/1176343949","volume":"5","author":"W. Foody","year":"1977","unstructured":"Foody, W., Hedayat, A.: On theory and applications of BIB designs with repeated blocks. Ann. Stat. 5, 932\u2013945 (1977)","journal-title":"Ann. Stat."},{"issue":"4","key":"9383_CR9","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1214\/aos\/1176344743","volume":"7","author":"W. Foody","year":"1979","unstructured":"Foody, W., Hedayat, A.: Note: Correction to \u201cOn Theory and Application of BIB Designs with Repeated Blocks\u201d. Ann. Stat. 7(4), 925 (1979)","journal-title":"Ann. Stat."},{"key":"9383_CR10","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-10514-2","volume-title":"Tensor Geometry","author":"C.T.J. Dodson","year":"1991","unstructured":"Dodson, C.T.J., Poston, T.: Tensor Geometry, 2nd edn. Graduate Texts in Mathematics, vol.\u00a0130. Springer, New York (1991)","edition":"2"},{"key":"9383_CR11","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1137\/0601002","volume":"1","author":"R.L. Graham","year":"1980","unstructured":"Graham, R.L., Li, S.-Y.R., Li, W.-C.W.: On the structure of t-designs. SIAM. J. Algebraic Discrete Methods 1, 8 (1980)","journal-title":"SIAM. J. Algebraic Discrete Methods"},{"key":"9383_CR12","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1137\/0602037","volume":"2","author":"N. Linial","year":"1981","unstructured":"Linial, N., Rothschild, B.: Incidence matrices of subsets\u2014a rank formula. SIAM. J. Algebraic Discrete Methods 2, 333 (1981)","journal-title":"SIAM. J. Algebraic Discrete Methods"},{"key":"9383_CR13","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":"9383_CR14","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":"9383_CR15","first-page":"27","volume":"58","author":"M. Kneser","year":"1955","unstructured":"Kneser, M.: Aufgabe 360. Jahresber. Dtsch. Math.-Ver. 58, 27 (1955) 2. Abteilung","journal-title":"Jahresber. Dtsch. Math.-Ver."},{"key":"9383_CR16","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L. Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A 25, 319\u2013324 (1978)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"1","key":"9383_CR17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s00493-004-0011-1","volume":"24","author":"J. Matou\u0161ek","year":"2004","unstructured":"Matou\u0161ek, J.: A combinatorial proof of Kneser\u2019s conjecture. Combinatorica 24(1), 163\u2013170 (2004)","journal-title":"Combinatorica"},{"key":"9383_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":"9383_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":"9383_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)","journal-title":"Theor. Comput. Sci."},{"key":"9383_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":"9383_CR22","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"}],"updated-by":[{"DOI":"10.1007\/s00453-015-0090-y","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2015,11,11]],"date-time":"2015-11-11T00:00:00Z","timestamp":1447200000000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9383-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9383-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9383-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,16]],"date-time":"2025-02-16T07:19:58Z","timestamp":1739690398000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9383-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,31]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9383"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9383-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,31]]}}}