{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:45Z","timestamp":1759638705332,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,3,23]],"date-time":"2016-03-23T00:00:00Z","timestamp":1458691200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,3,23]],"date-time":"2016-03-23T00:00:00Z","timestamp":1458691200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0914969"],"award-info":[{"award-number":["CCF-0914969"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217549"],"award-info":[{"award-number":["CCF-1217549"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00224-016-9671-7","type":"journal-article","created":{"date-parts":[[2016,3,23]],"date-time":"2016-03-23T02:11:01Z","timestamp":1458699061000},"page":"133-158","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Holant Problems for 3-Regular Graphs with Complex Edge Functions"],"prefix":"10.1007","volume":"59","author":[{"given":"Michael","family":"Kowalczyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin-Yi","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,3,23]]},"reference":[{"key":"9671_CR1","doi-asserted-by":"crossref","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer New York, Inc. (1998)","DOI":"10.1007\/978-1-4612-0701-6"},{"issue":"2-3","key":"9671_CR2","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"AA Bulatov","year":"2005","unstructured":"Bulatov, A.A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci. 348(2-3), 148\u2013186 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9671_CR3","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"JY Cai","year":"2013","unstructured":"Cai, J.Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: a dichotomy theorem. SIAM J. Comput. 42(3), 924\u20131029 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9671_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.01.021","volume":"461","author":"JY Cai","year":"2012","unstructured":"Cai, J.Y., Kowalczyk, M.: Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci. 461(1), 2\u201316 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"9671_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2012.12.043","volume":"494","author":"JY Cai","year":"2013","unstructured":"Cai, J.Y., Kowalczyk, M.: Partition functions on k-regular graphs with {0, 1}-vertex assignments and real edge functions. Theor. Comput. Sci. 494, 63\u201374 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9671_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"JY Cai","year":"2011","unstructured":"Cai, J.Y., Lu, P.: Holographic algorithms: from art to science. J. Comput. Syst. Sci. 77(1), 41\u201361 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9671_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. In: FOCS \u201908: proceedings of the 49th annual ieee symposium on foundations of computer science, pp 644\u2013653. IEEE Computer Society, Washington (2008)","DOI":"10.1109\/FOCS.2008.34"},{"issue":"23","key":"9671_CR8","doi-asserted-by":"publisher","first-page":"2468","DOI":"10.1016\/j.tcs.2010.10.039","volume":"412","author":"JY Cai","year":"2011","unstructured":"Cai, J.Y., Lu, P., Xia, M.: A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23), 2468\u20132485 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9671_CR9","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00037-012-0044-6","volume":"21","author":"JY Cai","year":"2012","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic reduction, interpolation and hardness. Comput. Complex. 21(4), 573\u2013604 (2012)","journal-title":"Comput. Complex."},{"issue":"2","key":"9671_CR10","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1016\/j.laa.2011.02.032","volume":"438","author":"JY Cai","year":"2013","unstructured":"Cai, J.Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates. Linear Algebra Appl. 438(2), 690\u2013707 (2013)","journal-title":"Linear Algebra Appl."},{"key":"9671_CR11","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs, vol. 54 (2007)","DOI":"10.1145\/1314690.1314691"},{"issue":"3\u20134","key":"9671_CR12","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"ME Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3\u20134), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms"},{"issue":"7","key":"9671_CR13","doi-asserted-by":"publisher","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"LA Goldberg","year":"2010","unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336\u20133402 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9671_CR14","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48(1), 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9671_CR15","doi-asserted-by":"crossref","unstructured":"Kowalczyk, M.: Classification of a class of counting problems using holographic reductions. In: Ngo, H.Q. (ed.) COCOON, lecture notes in computer science, vol. 5609, pp 472\u2013485. Springer (2009)","DOI":"10.1007\/978-3-642-02882-3_47"},{"key":"9671_CR16","unstructured":"Kowalczyk, M., Cai, J.Y.: Holant Problems for Regular Graphs with Complex Edge Functions. In: Marion, J.Y., Schwentick, T. (eds.) STACS 2010, pp 525\u2013536 (2010)"},{"key":"9671_CR17","doi-asserted-by":"crossref","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra and Geometry, 2nd edn. University of California Press, Berkeley (1951)","DOI":"10.1525\/9780520348097"},{"issue":"2","key":"9671_CR18","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"key":"9671_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9671_CR20","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9671_CR21","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"LG 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":"5","key":"9671_CR22","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"LG Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565\u20131594 (2008). (A preliminary version appeared in FOCS 2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9671_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"M Xia","year":"2007","unstructured":"Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1), 111\u2013125 (2007)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9671-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9671-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9671-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9671-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T00:34:34Z","timestamp":1655339674000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9671-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,23]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9671"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9671-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,3,23]]},"assertion":[{"value":"23 March 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}