{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:55:45Z","timestamp":1743008145558,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_60","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"712-723","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Symmetric Boolean Parity Holant Problems"],"prefix":"10.1007","author":[{"given":"Heng","family":"Guo","sequence":"first","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]},{"given":"Leslie G.","family":"Valiant","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"60_CR1","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1016\/j.ic.2006.02.002","volume":"204","author":"V. Arvind","year":"2006","unstructured":"Arvind, V., Kurur, P.P.: Graph isomorphism is in spp. Inf. Comput.\u00a0204(5), 835\u2013852 (2006)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Beigel, R., Buhrman, H., Fortnow, L.: Np might not be as easy as detecting unique solutions. In: STOC 1998: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 203\u2013208 (1998)","key":"60_CR2","DOI":"10.1145\/276698.276737"},{"issue":"1","key":"60_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"60_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/978-3-540-70575-8_53","volume-title":"Automata, Languages and Programming","author":"A.A. Bulatov","year":"2008","unstructured":"Bulatov, A.A.: The complexity of the counting constraint satisfaction problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 646\u2013661. Springer, Heidelberg (2008)"},{"key":"60_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-14165-2_24","volume-title":"Automata, Languages and Programming","author":"J.-Y. Cai","year":"2010","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 275\u2013286. Springer, Heidelberg (2010)"},{"doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Huang, S., Lu, P.: From holant to #CSP and back: Dichotomy for holantc problems. arXiv 1004.0803 (2010)","key":"60_CR6","DOI":"10.1007\/978-3-642-17517-6_24"},{"key":"60_CR7","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/1250790.1250850","volume-title":"STOC 2007: 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: STOC 2007: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 401\u2013410. ACM, New York (2007)"},{"key":"60_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-540-92182-0_51","volume-title":"Algorithms and Computation","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.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 568\u2013579. Springer, Heidelberg (2008)"},{"key":"60_CR9","volume-title":"FOCS 2008: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science","author":"J.Y. Cai","year":"2008","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic algorithms by fibonacci gates and holographic reductions for hardness. In: FOCS 2008: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Washington, DC, USA (2008)"},{"key":"60_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-02017-9_17","volume-title":"Theory and Applications of Models of Computation","author":"J.Y. Cai","year":"2009","unstructured":"Cai, J.Y., Lu, P., Xia, M.: A computational proof of complexity of some restricted counting problems. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol.\u00a05532, pp. 138\u2013149. Springer, Heidelberg (2009)"},{"key":"60_CR11","first-page":"715","volume-title":"STOC","author":"J.Y. Cai","year":"2009","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: Mitzenmacher, M. (ed.) STOC, pp. 715\u2013724. ACM, New York (2009)"},{"doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. In: FOCS 2010: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 427\u2013436 (2010)","key":"60_CR12","DOI":"10.1109\/FOCS.2010.48"},{"unstructured":"Cook, M., Bruck, J.: Implementability among predicates. Tech. rep., California Institute of Technology (2005)","key":"60_CR13"},{"doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classifications of boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications (2001)","key":"60_CR14","DOI":"10.1137\/1.9780898718546"},{"issue":"1","key":"60_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Inf. Comput.\u00a0125(1), 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"60_CR16","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. Graduate Texts in Mathematics, vol.\u00a0130. Springer, New York (1991)"},{"issue":"5","key":"60_CR17","doi-asserted-by":"publisher","first-page":"1970","DOI":"10.1137\/070690201","volume":"38","author":"M.E. Dyer","year":"2009","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: The complexity of weighted boolean #CSP. SIAM J. Comput.\u00a038(5), 1970\u20131986 (2009)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J. ACM\u00a054(6) (2007)","key":"60_CR18","DOI":"10.1145\/1314690.1314691"},{"unstructured":"Faben, J.: The complexity of counting solutions to generalised satisfiability problems modulo k. CoRR abs\/0809.1836 (2008)","key":"60_CR19"},{"issue":"1","key":"60_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"60_CR21","series-title":"LIPIcs","first-page":"493","volume-title":"STACS","author":"L.A. Goldberg","year":"2009","unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. In: Albers, S., Marion, J.Y. (eds.) STACS. LIPIcs, vol.\u00a03, pp. 493\u2013504. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"unstructured":"Guo, H., Huang, S., Lu, P., Xia, M.: The complexity of weighted boolean #csp modulo k. In: Schwentick, T., D\u00fcrr, C. (eds.) STACS. LIPIcs, vol.\u00a09, pp. 249\u2013260. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2011)","key":"60_CR22"},{"unstructured":"Kowalczyk, M., Cai, J.Y.: Holant problems for regular graphs with complex edge functions. In: The Proceeding of STACS (2010)","key":"60_CR23"},{"issue":"1","key":"60_CR24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM\u00a022(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. In: Proceedings of the 6th GI-Conference on Theoretical Computer Science, pp. 269\u2013276 (1982)","key":"60_CR25","DOI":"10.1007\/BFb0036487"},{"key":"60_CR26","first-page":"226","volume-title":"Proceedings of the Tenth Annual ACM Symposium on Theory of Computing","author":"T. Schaefer","year":"1978","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, p. 226. ACM, New York (1978)"},{"issue":"2","key":"60_CR27","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"Toda, S., Ogiwara, M.: Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput.\u00a021(2), 316\u2013328 (1992)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"60_CR28","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci.\u00a047(1), 85\u201393 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"60_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"60_CR30","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 J. Comput.\u00a031(4), 1229\u20131254 (2002)","journal-title":"SIAM J. Comput."},{"key":"60_CR31","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/FOCS.2006.7","volume-title":"FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2006","unstructured":"Valiant, L.G.: Accidental algorthims. In: FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517. IEEE Computer Society Press, Washington, DC, USA (2006)"},{"issue":"5","key":"60_CR32","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L.G. Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM J. Comput.\u00a037(5), 1565\u20131594 (2008)","journal-title":"SIAM J. Comput."},{"key":"60_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-12200-2_50","volume-title":"LATIN 2010: Theoretical Informatics","author":"L.G. Valiant","year":"2010","unstructured":"Valiant, L.G.: Some observations on holographic algorithms. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 577\u2013590. Springer, Heidelberg (2010)"}],"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-642-22006-7_60","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:13:21Z","timestamp":1558296801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_60"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}