{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:22:22Z","timestamp":1770740542326,"version":"3.49.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,11,17]],"date-time":"2015-11-17T00:00:00Z","timestamp":1447718400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00037-015-0118-3","type":"journal-article","created":{"date-parts":[[2015,11,17]],"date-time":"2015-11-17T16:15:58Z","timestamp":1447776958000},"page":"255-304","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["A Dichotomy for Real Weighted Holant Problems"],"prefix":"10.1007","volume":"25","author":[{"given":"Sangxia","family":"Huang","sequence":"first","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,17]]},"reference":[{"key":"118_CR1","doi-asserted-by":"crossref","unstructured":"Lenore Blum, Felipe Cucker, Michael Shub & Steve Smale (1998). Complexity and real computation. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"118_CR2","unstructured":"B\u00e9la Bollob\u00e1s (1998). Modern graph theory, volume 184 of Graduate Texts in Mathematics. Springer-Verlag."},{"key":"118_CR3","unstructured":"Graham Brightwell & Peter Winkler (2005). Counting Eulerian circuits is #P-Complete. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, Vancouver, BC, Canada, 259\u2013262. Society for Industrial and Applied Mathematics."},{"key":"118_CR4","unstructured":"Valentin E. Brimkov & Stefan S. Dantchev (2000). On the com plexity of integer programming in the Blum-Shub-Smale computational model. In Proceedings of Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, International Conference 2000, Sendai, Japan, 286\u2013300. Springer-Verlag."},{"key":"118_CR5","doi-asserted-by":"crossref","unstructured":"Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius & David Richerby (2009). The complexity of weighted boolean #CSP with mixed signs. Theoretical Computer Science 410, 3949\u20133961.","DOI":"10.1016\/j.tcs.2009.06.003"},{"issue":"1","key":"118_CR6","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"Andrei A. Bulatov","year":"2006","unstructured":"Bulatov Andrei A. (2006) A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM 53(1): 66\u2013120","journal-title":"Journal of the ACM"},{"key":"118_CR7","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov (2013). The complexity of the counting constraint satisfaction problem. Journal of the ACM 60(5), 34.","DOI":"10.1145\/2528400"},{"key":"118_CR8","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov & V\u00edctor Dalmau (2007). Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation 205(5), 651\u2013678.","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"118_CR9","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov & Martin Grohe (2004). The complexity of partition functions. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku, Fin land, 294\u2013306. Springer-Verlag.","DOI":"10.1007\/978-3-540-27836-8_27"},{"key":"118_CR10","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov & Martin Grohe (2005). The complexity of partition functions. Theoretical Computer Science 348(2\u20133), 148\u2013186.","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"118_CR11","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Xi Chen & Pinyan Lu (2011a). Non-negatively weighted #CSP: an effective complexity dichotomy. In Proceedings of the 26th IEEE Conference on Computational Complexity, San Jose, CA, USA, 45\u201354. IEEE Computer Society Press.","DOI":"10.1109\/CCC.2011.32"},{"issue":"3","key":"118_CR12","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"Jin-Yi Cai","year":"2013","unstructured":"Cai Jin-Yi, Chen Xi, Lu Pinyan. (2013) Graph homomorphisms with complex values: a dichotomy theorem. SIAM Journal on Comput 42(3): 924\u20131029","journal-title":"SIAM Journal on Comput"},{"key":"118_CR13","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Heng Guo & Tyson Williams (2013b). A complete dichotomy rises From The capture Of vanishing signatures. In Pro ceedings of the 45th Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA, 635\u2013644. ACM Press.","DOI":"10.1145\/2488608.2488687"},{"issue":"3","key":"118_CR14","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s00453-012-9626-6","volume":"64","author":"Jin-Yi Cai","year":"2012","unstructured":"Cai Jin-Yi, Huang Sangxia, Lu Pinyan. (2012) From Holant to #CSP and back: dichotomy for Holant c problems. Algorithmica 64(3): 511\u2013533","journal-title":"Algorithmica"},{"key":"118_CR15","unstructured":"Jin-Yi Cai & Michael Kowalczyk (2010). A dichotomy for k-regular graphs with {0, 1}-vertex assignments And real edge functions. In Pro ceedings of the 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic, 328\u2013339. Springer-Verlag."},{"key":"118_CR16","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2008). Holographic algorithms by Fibonacci gates And holographic reductions for hardness. In Proceed ings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 644\u2013653. IEEE Computer Society Press.","DOI":"10.1109\/FOCS.2008.34"},{"key":"118_CR17","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2009). Holant problems and counting CSP. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, Maryland, USA, 715\u2013724. ACM Press.","DOI":"10.1145\/1536414.1536511"},{"key":"118_CR18","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2010). Holographic algorithms with matchgates capture precisely tractable planar #CSP. In Proceed ings of the 51st Annual IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 427\u2013436. IEEE Computer Society Press."},{"issue":"23","key":"118_CR19","doi-asserted-by":"crossref","first-page":"2468","DOI":"10.1016\/j.tcs.2010.10.039","volume":"412","author":"Jin-Yi Cai","year":"2011","unstructured":"Cai Jin-Yi, Lu Pinyan, Xia Mingji. (2011) A computational proof of complexity of some restricted counting problems. Theoretical Computer Science 412(23): 2468\u20132485","journal-title":"Theoretical Computer Science"},{"key":"118_CR20","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2013c). Holographic algo rithms by Fibonacci gates. Linear Algebra and its Applications 438(2), 690\u2013707.","DOI":"10.1016\/j.laa.2011.02.032"},{"key":"118_CR21","doi-asserted-by":"crossref","unstructured":"Nadia Creignou, Sanjeev Khanna & Madhu Sudan (2001). Com plexity classifications of boolean constraint satisfaction problems. Society for Industrial and Applied Mathematics. ISBN 0-89871-479-6.","DOI":"10.1137\/1.9780898718546"},{"key":"118_CR22","doi-asserted-by":"crossref","unstructured":"C. T. J. Dodson & T. Poston (1991). Tensor geometry. Springer- Verlag.","DOI":"10.1007\/978-3-642-10514-2"},{"key":"118_CR23","doi-asserted-by":"crossref","unstructured":"Martin E. Dyer, Leslie Ann Goldberg & Mark Jerrum (2009). The complexity of weighted boolean #CSP. SIAM Journal on Com puting 38(5), 1970\u20131986.","DOI":"10.1137\/070690201"},{"key":"118_CR24","doi-asserted-by":"crossref","unstructured":"Martin E. Dyer, Leslie Ann Goldberg &Mike Paterson (2007). On counting homomorphisms to directed acyclic graphs. Journal of the ACM 54(6).","DOI":"10.1145\/1314690.1314691"},{"key":"118_CR25","unstructured":"Martin E. Dyer & Catherine S. Greenhill (2000). The com plexity of counting graph homomorphisms (extended abstract). In Pro ceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algo rithms, San Francisco, CA, USA, 246\u2013255. Society for Industrial and Applied Mathematics."},{"issue":"3","key":"118_CR26","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1002\/rsa.20036","volume":"25","author":"Martin E. Dyer","year":"2004","unstructured":"Dyer Martin E., Greenhill Catherine S. (2004) Corrigendum: The complexity of counting graph homomorphisms. Random Structures and Algorithms 25(3): 346\u2013352","journal-title":"Random Structures and Algorithms"},{"key":"118_CR27","doi-asserted-by":"crossref","unstructured":"Martin E. Dyer & David Richerby (2010). On the complexity of #CSP. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 725\u2013734. ACM Press.","DOI":"10.1145\/1806689.1806789"},{"key":"118_CR28","unstructured":"Martin E. Dyer & David Richerby (2011). The #CSP dichotomy is decidable. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, Dortmund, Germany, 261\u2013 272. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik."},{"key":"118_CR29","unstructured":"John Faben (2008). The complexity of counting solutions to generalised satisfiability problems modulo k. CoRR abs\/0809.1836."},{"key":"118_CR30","doi-asserted-by":"crossref","unstructured":"Tom\u00e1s Feder & Moshe Y. Vardi (1998). The computational struc ture of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM Journal on Computing 28(1), 57\u2013104.","DOI":"10.1137\/S0097539794266766"},{"issue":"3","key":"118_CR31","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1007\/s00453-010-9463-4","volume":"63","author":"Qi Ge","year":"2012","unstructured":"Ge Qi, Stefankovic Daniel. (2012) The complexity of counting Eulerian tours in 4-regular graphs. Algorithmica 63(3): 588\u2013601","journal-title":"Algorithmica"},{"key":"118_CR32","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg, Martin Grohe, Mark Jerrum & Marc Thurley (2010). A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing 39(7), 3336\u20133402.","DOI":"10.1137\/090757496"},{"key":"118_CR33","unstructured":"Heng Guo, Sangxia Huang, Pinyan Lu & Mingji Xia (2011). The complexity of weighted boolean #CSP modulo k. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, Dortmund, Germany, 249\u2013260. Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik."},{"key":"118_CR34","doi-asserted-by":"crossref","unstructured":"Heng Guo, Pinyan Lu & Leslie G. Valiant (2013). The complex ity of symmetric boolean parity Holant problems. SIAM Journal on Computing 42(1), 324\u2013356.","DOI":"10.1137\/100815530"},{"key":"118_CR35","doi-asserted-by":"crossref","unstructured":"Pavol Hell & Jaroslav Ne\u0161et\u0159il (1990). On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48(1), 92\u2013110.","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"118_CR36","doi-asserted-by":"crossref","unstructured":"Sangxia Huang & Pinyan Lu (2012). A dichotomy for real weighted Holant problems. In Proceedings of the 27th IEEE Conference on Com putational Complexity, Porto, Portugal, 96\u2013106. IEEE Computer Soci ety Press.","DOI":"10.1109\/CCC.2012.16"},{"issue":"1","key":"118_CR37","first-page":"253","volume":"31","author":"E. Ising","year":"1925","unstructured":"Ising E. (1925) Beitrag zur Theorie des Ferromagnetismus. Zeitschrift f\u00fcr Physik A Hadrons and Nuclei 31(1): 253\u2013258","journal-title":"Zeitschrift f\u00fcr Physik A Hadrons and Nuclei"},{"key":"118_CR38","doi-asserted-by":"crossref","unstructured":"F. Jaeger, D. L. Vertigan & D. J. A. Welsh (1990). On the com putational complexity of the Jones and Tutte polynomials. Proceedings of the Cambridge Philosophical Society 108, 35\u201353.","DOI":"10.1017\/S0305004100068936"},{"key":"118_CR39","unstructured":"Ker-I Ko (1991). Complexity theory of real functions. Birkhauser Boston Inc., Cambridge, MA, USA."},{"key":"118_CR40","unstructured":"Michael Kowalczyk & Jin-Yi Cai (2010). Holant problems for reg ular graphs with complex edge functions. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France, 525\u2013536. Schloss Dagstuhl - Leibniz-Zentrum fuer Infor matik."},{"issue":"1","key":"118_CR41","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"Richard E. Ladner","year":"1975","unstructured":"Ladner Richard E. (1975) On the structure of polynomial time reducibility. Journal of the ACM 22(1): 155\u2013171","journal-title":"Journal of the ACM"},{"key":"118_CR42","doi-asserted-by":"crossref","unstructured":"Michel Las Vergnas (1988). On the evaluation at (3, 3) of the Tutte polynomial of a graph. Journal of Combinatorial Theory, Series B 45(3), 367\u2013372.","DOI":"10.1016\/0095-8956(88)90079-2"},{"key":"118_CR43","doi-asserted-by":"crossref","unstructured":"H. W. Jr. Lenstra (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research 8(4).","DOI":"10.1287\/moor.8.4.538"},{"key":"118_CR44","doi-asserted-by":"crossref","unstructured":"Milena Mihail & Peter Winkler (1996). On the number of Eulerian orientations of a graph. Algorithmica 16(4\/5), 402\u2013414.","DOI":"10.1007\/BF01940872"},{"key":"118_CR45","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou & Stathis Zachos (1982). Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science, 269\u2013276.","DOI":"10.1007\/BFb0009651"},{"key":"118_CR46","unstructured":"H. Pollard & H.G. Diamond (1998). The theory of algebraic num bers. Phoenix Edition Series. Dover Publications, Inc."},{"key":"118_CR47","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1979). The complexity of computing the perma nent. Theoretical Computer Science 8, 189\u2013201.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"118_CR48","unstructured":"Leslie G. Valiant (2006). Accidental algorithms. In FOCS, 509\u2013517."},{"key":"118_CR49","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (2008). Holographic algorithms. SIAM Journal on Computing 37(5), 1565\u20131594.","DOI":"10.1137\/070682575"},{"key":"118_CR50","unstructured":"Leslie G. Valiant (2010). Some observations on holographic algo rithms. In Proceedings of 9th Latin American Theoretical Informatics Symposium, Oaxaca, Mexico, 577\u2013590. Springer-Verlag."},{"key":"118_CR51","doi-asserted-by":"crossref","unstructured":"Dirk Vertigan (2005). The computational complexity of Tutte invari ants for planar graphs. SIAM Journal on Computing 35(3), 690\u2013712.","DOI":"10.1137\/S0097539704446797"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0118-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0118-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0118-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0118-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,17]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["118"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0118-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,17]]}}}